ilhas
Problem
Um estado espalhado pelas ilhas da Oceania decidiu criar uma rede de estradas (ou melhor, pontes). Cada ponte pode ser navegada em ambas as direções. Foi desenvolvido um plano de sequenciamento para a construção de pontes e sabe-se que após a construção de todas as pontes será possível passar por cima delas de ilha em ilha (talvez por algumas ilhas intermediárias
No entanto, este momento pode chegar antes que todas as pontes sejam construídas. Você precisa determinar um número mínimo de pontes, após a construção das quais (na ordem determinada pelo plano), será possível ir de qualquer ilha a qualquer outra.
Entrada
A primeira linha contém dois números: o número de ilhas N (1≤N≤10000) e o número de pontes no plano M (1≤M≤50000). Depois, há M linhas, cada uma contendo dois números x e y (1≤x,y≤N) - os números das cidades conectadas pela próxima ponte no plano.
Saída
O programa deve gerar um único número - o número mínimo de pontes construídas, após o qual será possível ir de uma ilha a outra.
| Entrada |
Saída |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |