Isole
Problem
Uno stato sparso sulle isole dell'Oceania ha deciso di creare una rete di strade (o meglio, di ponti). Ogni ponte può essere navigato in entrambe le direzioni. È stato sviluppato un piano sequenziale per la costruzione dei ponti ed è noto che dopo la costruzione di tutti i ponti sarà possibile attraversarli da un'isola all'altra (magari attraverso alcune isole intermedie
Tuttavia, questo momento potrebbe arrivare prima che tutti i ponti siano costruiti. È necessario determinare un numero minimo di ponti, dopo la cui costruzione (nell'ordine determinato dal piano), sarà possibile spostarsi da qualsiasi isola a qualsiasi altra.
Input
La prima riga contiene due numeri: il numero di isole N (1≤N≤10000) e il numero di ponti in pianta M (1≤M≤50000). Poi ci sono M linee, ciascuna contenente due numeri x e y (1≤x,y≤N) - i numeri delle città che sono collegate dal ponte successivo nella pianta.
Uscita
Il programma dovrebbe produrre un singolo numero: il numero minimo di ponti costruiti, dopodiché sarà possibile spostarsi da un'isola all'altra.
| Input |
Uscita |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |