Fișierul intrare/ieșire	orase.in, orase.out	Sursă	Cupa Dorinel 2015
Autor	Tudor Coman	Adăugată de	Tudor Coman • tudorcoman
Timp de execuție pe test	3.15 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4

Vezi soluțiile trimise | Statistici

Orase

Dorinel este un inginer la o firmă de software. Șefa lui, pe nume Nușa, i-a dat temă să facă un program mai special. Se dau N localități, numerotate de la 1 la N. Aceste orașe sunt conectate prin M șosele (o șosea este descrisă prin 2 numere x și y ce reprezintă capetele drumului). Un județ este format din mai multe orașe, conectate prin una sau mai multe șosele). Un oraș izolat este un oraș ce nu este conectat la nici un alt oraș.

Cerință

1. Să se determine numărul de orașe izolate.
2. Dându-se T întrebări de forma (x, y) să se determine numărul minim de șosele dintre x și y.
3. Să se determine numărul de județe.

Date de intrare

Fișierul de intrare orase.in conține pe prima linie două numere N și M. Următoarele M linii descriu șoselele. Pe linia M + 1 se dă un număr T, care reprezintă numărul de întrebări de la cerința 2, iar apoi pe următoarele T linii se dau două numere x și y ce reprezintă întrebarea (x, y).

Date de ieșire

În fișierul de ieșire orase.out se află pe prima linie răspunsul la prima cerință. Pe următoarele T linii se află răspunsurile la cerința a doua, iar pe ultima linie se află răspunsul la întrebarea a treia.

Restricții și precizări

• 1 ≤ N, M ≤ 100000
• 1 ≤ T ≤ 1000
• 1 ≤ x, y ≤ N
• Un județ poate fi format doar dintr-un oraș.
• Dacă rezolvați toate cerințele, Dorinel vă va răsplăti cu 100 de puncte și poate și cu 1 leu (nu promite nimic).

Exemplu

Explicație

...