P8014 [COCI 2013/2014 #4] SUMO

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.

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 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.

**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](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T3 SUMO**_。 Translated by ChatGPT 5