Kampanja

Οι εκλογές πλησιάζουν, οπότε ο Πρόεδρος Amabo Kcarab σχεδιάζει μια περιοδεία στις Ηνωμένες Πολιτείες, με ομιλίες σε WDC και LA. Για να παρέχει επαρκή ασφάλεια, η Μυστική Υπηρεσία πρέπει να παρακολουθεί συνεχώς όλες τις πόλεις που θα περάσει ο Πρόεδρος (συμπεριλαμβανομένων των WDC και LA).
Φυσικά, ο ομοσπονδιακός προϋπολογισμός πρέπει να δαπανηθεί υπεύθυνα, επομένως ο Πρόεδρος δεν θα χρησιμοποιεί το AF1, αλλά θα ταξιδέψει με αυτοκίνητο. Επίσης, η Μυστική Υπηρεσία θα προγραμματίσει την περιοδεία του Προέδρου από το WDC στο LA και πίσω στο WDC έτσι ώστε να χρειάζεται να παρακολουθείται ο ελάχιστος δυνατός αριθμός πόλεων.
Για αυτό το πρόβλημα, ας υποθέσουμε ότι οι Πολιτείες αποτελούνται από ~N~ πόλεις, που συμβολίζονται με αριθμούς από το ~1~ έως το ~N~, και ~M~ διαπολιτειακούς δρόμους μονοκατευθηντικούς, με κάθε διαπολιτειακό να συνδέει δύο διαφορετικές πόλεις. Το WDC είναι η πόλη νούμερο ~1~ και LA η νούμερο ~2~.
Γράψτε ένα πρόγραμμα για να υπολογίσετε τον ελάχιστο αριθμό πόλεων που πρέπει να παρακολουθούνται έτσι ώστε να υπάρχει υπάρχει μια διαδρομή από το WDC στο LA και πίσω στο WDC που περνά μόνο από παρακολουθούμενες πόλεις.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους δύο ακέραιους ~N~ και ~M (2 \le N \le 100,\,2 \le M \le 200)~, τον αριθμό των πόλεων και τον αριθμό των διαπολιτειακών που συνδέουν τις πόλεις, αντίστοιχα.
Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει δύο διαφορετικούς ακέραιους αριθμούς ~A~, ~B~ ~(1 \le A, B \le N)~, την αρχική και την τελική πόλη που εξυπηρετείται από τον δεδομένο διαπολιτειακό. Δεν υπάρχουν δύο διαπολιτειακοί που να συνδέουν τις ίδιες δύο πόλεις με την ίδια κατεύθυνση, αλλά δύο διαπολιτειακοί μπορούν να συνδέσουν τις ίδιες δύο πόλεις σε αντίθετες κατευθύνσεις.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον ελάχιστο αριθμό πόλεων που χρειάζεται να παρακολουθούνται.

Βαθμολογία

Σε δεδομένα δοκιμής συνολικής αξίας ~20~ πόντων, το ~N~ θα είναι το πολύ ~20~.
Σημείωση: Τα δεδομένα δοκιμής θα διασφαλίσουν ότι μια λύση θα υπάρχει πάντα.

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

input

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

output

6

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

Ο Πρόεδρος μπορεί να πάρει την ακόλουθη διαδρομή: ~1~ -> ~2~ -> ~3~ -> ~4~ -> ~2~ -> ~6~ -> ~3~ -> ~4~ -> ~5~ -> ~1~. Αφού χρειάζεται να περάσει από κάθε πόλη τουλάχιστον μία φορά, η λύση είναι ~6~.

input

9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1

output

6