Sumo

Σε ένα ιαπωνικό μοναστήρι, γνωστό κατά τα άλλα για τη σοβαρή νηστεία και την ασκητική ζωή, ο Προϊστάμενος του τμήματος πάλης σούμο αποφάσισε να διοργανώσει προπονητικούς αγώνες για τους ~N~ μαχητές του. Προσδιόρισε την ακριβή σειρά των ~M~ αγώνων και των συμμετεχόντων (δύο μαχητές αντιμετωπίζουν ο ένας τον άλλον ανά αγώνα).

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

Βοηθήστε τον επικεφαλή! Για ένα δεδομένο πρόγραμμα αγώνων, προσδιορίστε τον αριθμό του πρώτου αγώνα όπου δύο μαχητές από την ίδια ομάδα πρέπει να αντιμετωπίσουν ο ένας τον άλλον, υπό την προϋπόθεση ότι θα τους χωρίσουμε με τον καλύτερο δυνατό τρόπο, ώστε ο απαιτούμενος αγώνας να γίνει το αργότερο δυνατόν. Σε όλα τα δεδομένα δοκιμών, μια τέτοια μάχη σίγουρα θα συμβεί.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 100\,000)~, τον αριθμό των μαχητών. Τα μαχητικά σημειώνονται με αριθμούς από 1 έως ~N~.

Η δεύτερη γραμμή εισόοδυ περιέχει τον ακέραιο αριθμό ~M\;(1 \leq M \leq 300\,000)~, τον αριθμό των αγώνων.

Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει αγώνες με τη σειρά που πρέπει να διεξαχθούν. Κάθε γραμμή περιέχει δύο διαφορετικούς ακέραιους αριθμούς από το διάστημα ~[1,\;N]~: τις ετικέτες των μαχητών που πρόκειται να αντιμετωπίσουν ο ένας τον άλλον.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον τακτικό αριθμό (από 1 έως ~M~) του απαιτούμενου αγώνα.

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

input

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

output

5

input

6
8
1 2
3 4
5 6
1 3
1 6
4 5
2 4
2 6

output

6