Logičari

Μια ομάδα τέλειων θεωρητικών της Λογικής έλαβε ξανά αίτημα να γίνουν οι κύριοι πρωταγωνιστές ενός νέου παζλ λογικής. Πρέπει τώρα να συμφωνήσουν ποιος από τους ~n~ της ομάδας θα πρέπει να συμμετάσχει.

Αυτή τη φορά το λογικό παζλ λαμβάνει χώρα σε ένα μη κατευθυνόμενο γράφο με n κόμβους και λογικά, n ακμές. Κάθε ακμή συνδέει δύο διαφορετικούς κόμβους και μεταξύ οποιωνδήποτε δύο κόμβων υπάρχει το πολύ μία ακμή. Επιπλέον, ο γράφος είναι συνδεδεμένος, που σημαίνει ότι είναι δυνατή η μετάβαση από οποιονδήποτε κόμβο σε οποιονδήποτε άλλο μέσω μιας ακολουθίας ακμών. Για κάθε κόμβο θα υπάρχει ένας θεωρητικός της Λογικής που βρίσκεται σε αυτόν τον κόμβο και καθένας τους είναι σε θέση να δει ακριβώς όλους τους θεωρητικούς της Λογικής των οποίων οι κόμβοι συνδέονται με μια ακμή με τον δικό του κόμβο.

Ήδη υποψιάζονταν ότι το κόλπο για να λύσουν το λογικό παζλ μπορεί να σχετίζεται με το χρώμα των ματιών τους, και έτσι αποφάσισαν να διαταχθούν με τέτοιο τρόπο έτσι ώστε κάθε ένας τους να βλέπει ακριβώς έναν άλλον με μπλε μάτια. Όπως συμβαίνει συνήθως, κανένας από τους "λογικούς" δεν μπορεί να δει το δικό του χρώμα ματιών, πράγμα που σημαίνει ότι ακόμη και οι θεωρητικοί της Λογικής με μπλε μάτια πρέπει να δουν ακριβώς ένα άλλο άτομο με μπλε μάτια.

Ποιος είναι ο ελάχιστος αριθμός θεωρητικών της Λογικής με μπλε μάτια που χρειάζονται για να γίνει η απαιτούμενη διάταξη;

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ - τον αριθμό των κόμβων στο γράφημα, καθώς και τον αριθμό των θεωρητικών της Λογικής.

Οι ακόλουθες ~n~ γραμμές περιέχουν ζεύγη ακεραίων που αντιπροσωπεύουν τις ακμές του γραφήματος. Κάθε ακμή συνδέει δύο διαφορετικούς κόμβους και καμία ακμή δεν επαναλαμβάνεται δύο φορές στην είσοδο.

Έξοδος

Εάν δεν υπάρχει η απαιτούμενη διάταξη, στην πρώτη και μοναδική γραμμή εκτυπώστε -1.

Διαφορετικά, στην πρώτη και μοναδική γραμμή εκτυπώστε τον απαιτούμενο ελάχιστο αριθμό θεωρητικών της Λογικής με μπλε μάτια.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	Κάθε θεωρητικός της Λογικής βλέπει ακριβώς δύο άλλους.
2	10	~3 \le n \le 20~
3	40	~3 \le n \le 1000~
4	50	~3 \le n \le 100\,000~

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

input

4
1 2
2 3
3 4
4 1

output

2

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

Οι θεωρητικοί της Λογικής με μπλε μάτια θα μπορούσαν για παράδειγμα να είναι αυτοί στους κόμβους 1 και 2.

input

3
1 2
2 3
3 1

output

-1

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

Αν μόνο ένας από τους θεωρητικούς της Λογικής έχει μπλε μάτια, τότε σίγουρα δεν μπορεί να δει κανέναν άλλον με μπλε μάτια. Εάν υπάρχουν δύο ή περισσότεροι με μπλε μάτια, τότε σίγουρα κάποιος θα δει περισσότερα από ένα άτομα με μπλε μάτια.

input

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

output

4