Problem
Ein Staat, der auf den Inseln Ozeaniens verstreut war, beschloss, ein Netz von Autobahnen (oder vielmehr Brücken) zu schaffen. Jede Brücke kann in beide Richtungen befahren werden. Es wurde ein Brückenreihenfolgenplan entwickelt und es ist bekannt, dass nach dem Bau aller Brücken von jeder Insel zu jeder Insel gefahren werden kann (möglicherweise durch einige Zwischeninseln
Dieser Moment kann jedoch kommen, bevor alle Brücken gebaut werden. Sie müssen eine so minimale Anzahl von Brücken definieren, nach deren Bau (in der vom Plan definierten Reihenfolge) Sie von jeder Insel zu jeder anderen gelangen können.
Eingabe
Die erste Zeile enthält zwei Zahlen: die Anzahl der Inseln N (1≤N≤10000) und die Anzahl der Brücken im Plan M (1≤M≤50000). Als nächstes kommt M von Zeilen, jede enthält zwei Zahlen x und y (1≤x,y≤N) - die Zahlen der Städte, die die nächste Brücke im Plan verbindet.
Ausgabe
Das Programm muss eine einzige Zahl ausgeben - die Mindestanzahl an Brücken, die gebaut wurden, um von jeder Insel zu jeder anderen zu gelangen.
| Eingabe |
Ausgabe |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |