Fişierul intrare/ieşire:orase.in, orase.outSursăCupa Dorinel 2015
AutorTudor ComanAdăugată detudorcomanTudor Coman tudorcoman
Timp execuţie pe test3.15 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Orase

Dorinel este un inginer la o firmă de software. Şefa lui, pe nume Nushaka, 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 + 2 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 ≤ 100000
  • 1 ≤ M ≤ 25000
  • 1 ≤ T ≤ 1000
  • 1 ≤ x, y ≤ N
  • Un judeţ este format din unul sau mai multe oraşe.
  • Dacă pentru cerinţa 2 nu se poate ajunge din x în y se va afişa -1.
  • Pentru cerinţa 1 se acordă 30% din punctaj.
  • Pentru cerinţa 2 se acordă 30% din punctaj.
  • Pentru cerinţa 3 se acordă 40% din punctaj.
  • 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

orase.inorase.outImagine
7 5
1 2
3 7
2 4
4 5
2 5
3
3 7
1 4
3 6
1
1
2
-1
3

Explicaţie

Singurul oraş izolat este 6. Pentru a ajunge din 3 în 7 se foloseşte şoseaua 3-7. Pentru a ajunge din 1 în 4 se folosesc şoselele 1-2 şi 2-4. Cum 6 este izolat, nu putem ajunge din 3 în 6. Cele 3 judeţe sunt 1-2-4-5, 3-7 şi 6.

Trebuie sa te autentifici pentru a trimite solutii. Click aici