îles
Problem
Un État dispersé sur les îles d'Océanie a décidé de créer un réseau de routes (ou plutôt de ponts). Chaque pont peut être navigué dans les deux sens. Un plan de séquencement pour la construction de ponts a été élaboré et on sait qu'après la construction de tous les ponts, il sera possible de les traverser en voiture de chaque île à chacune (peut-être à travers certaines îles intermédiaires
Cependant, ce moment peut arriver avant que tous les ponts ne soient construits. Vous devez déterminer un tel nombre minimum de ponts, après la construction desquels (dans l'ordre déterminé par le plan), il sera possible de se rendre de n'importe quelle île à n'importe quelle autre.
Entrée
La première ligne contient deux nombres : le nombre d'îles N (1≤N≤10000) et le nombre de ponts dans le plan M (1≤M≤50000). Ensuite, il y a M lignes, chacune contenant deux nombres x et y (1≤x,y≤N) - les numéros des villes qui sont reliées par le pont suivant dans le plan.
Sortie
Le programme devrait produire un seul nombre - le nombre minimum de ponts construits, après quoi il sera possible de se rendre de n'importe quelle île à n'importe quelle autre.
| Entrée |
Sortie |
4 5
1 2
1 3
2 3
3 4
4 1
4 |