Problem Description

There are $N$ players participating in $M$ one-on-one matches, and the match order has already been fixed.

Now you need to divide these players into $2$ teams, so that players meet opponents from the same team as late as possible.

Output the match index of the first match in which a player meets a player from the same team, under the optimal division.

Input Format

The first line contains a positive integer $N$, meaning there are $N$ players.

The second line contains a positive integer $M$, meaning there are $M$ matches.

The next $M$ lines each contain two positive integers $A_i$ and $B_i$, meaning the players in match $i$ are player $A_i$ and player $B_i$.

Output Format

Output one line containing a positive integer, the match index of the first match in which a player meets a player from the same team under the optimal team division.

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

5

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

6

Hint

Sample Explanation #1

$[1,3,5]$ are in one team, and $[2,4]$ are in the other team.

It can be proven that this is the optimal division.

Constraints

For $100\%$ of the testdata, $1\le A_i,B_i\le N\le 10^5$ and $1\le M\le 3\times 10^5$.

Source

The score of this problem follows the original COCI settings, with a full score of $100$.

Translated from COCI2013-2014 CONTEST #4 T3 SUMO。

Translated by ChatGPT 5