Mostovi

Όταν ο Leonhard Euler έλυσε το περίφημο πρόβλημα της γέφυρας του Königsberg, δεν είχε ιδέα ότι είχε ανακαλύψει μια εντελώς νέα περιοχή των μαθηματικών -τη θεωρία γραφημάτων!

Δυστυχώς, το πρόβλημα της γέφυρας του Königsberg είναι πάρα πολύ εύκολο για τους προγραμματιστές αυτής της εποχής, έτσι ο Euler σκέφτηκε ένα άλλο πρόβλημα -το πρόβλημα της γέφυρας του Ζάγκρεμπ!

Οι γέφυρες του Ζάγκρεμπ σχηματίζουν ένα γράφημα με ~n~ κόμβους και ~m~ ακμές, όπου οι ακμές αντιπροσωπεύουν τις γέφυρες και οι κόμβοι τις νησίδες του ποταμού. Το γράφημα είναι συνδεδεμένο, με άλλα λόγια, είναι δυνατόν να φτάσει κανείς από οποιονδήποτε κόμβο σε οποιονδήποτε άλλο ταξιδεύοντας μέσω των ακμών. Τώρα ο Euler ρώτησε, πόσες ακμές υπάρχουν έτσι ώστε μετά την αφαίρεσή τους το γράφημα να γίνεται ασύνδετο;

Και πάλι, ο Euler δεν γνώριζε ότι αυτό το πρόβλημα είναι διάσημο και σήμερα (αυτά τα καταραμένα Codeforces ιστολόγια!). Έτσι, ο συγγραφέας αυτού του προβλήματος αποφάσισε να σας δώσει ένα ακόμα πιο δύσκολο: Πόσες ακμές υπάρχουν τέτοιες ώστε μετά την αφαίρεση των κόμβων που συνδέουν, οι εναπομείνασες ~n - 2~ ακμές να αποσυνδέονται;

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~n~ και ~m\;(4 \le n \le 100\;000,\;n - 1 \le m \le 300\;000)~- τον αριθμό των κόμβων και ακμών αντίστοιχα.

Κάθε μία από τις επόμενες ~m~ γραμμές θα περιέχει τους ακέραιους αριθμούς ~a_{i}~ και ~b_{i}\;(1 \le a_{i},b_{i} \le n)~ - αυτό θα σημαίνει ότι οι κόμβοι ~a_{i}~ και ~b_{i}~ συνδέονται με μια ακμή.

Δεν υπάρχουν βρόγχοι ή πολλαπλές ακμές.

Έξοδος

Σε μία γραμμή εξάγετε τον αριθμό των ακμών με τη δεδομένη ιδιότητα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~13~	~n \le 100, \;m \le 300~
~2~	~17~	~n \le 1000, \;m \le 3000~
~3~	~25~	~n \le 1000~
~4~	~12~	~m-n \le 20~
~5~	~43~	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

4 5
1 2
2 3
3 4
4 1
1 3

output

1

Επεξήγηση του πρώτου παραδείγματος:

Αφαιρώντας την ακμή ~(1,\;3)~ και τους αντίστοιχους κόμβους ~1~ και ~1~, το γράφημα που απομένει έχει δύο συνδεδεμένες συνιστώσες, τον κόμβο ~2~ και τον κόμβο ~4~. Με άλλα λόγια, δεν είναι συνδεδεμένο. Είναι εύκολο να ελεγχθεί ότι είναι η μόνη ακμή με αυτή την ιδιότητα.

input

6 7
1 2
2 4
2 6
3 5
6 1
4 3
2 5

output

4

Επεξήγηση του δεύτερου παραδείγματος:

Οι ακμές με τη συγκεκριμένη ιδιότητα είναι οι ~(1,\;2)~, ~(2,\;4)~, ~(2,\;6)~ και ~(2,\;5)~.