P8014 [COCI 2013/2014 #4] SUMO

有 $N$ 个选手参加 $M$ 场 $1$ 对 $1$ 的比赛，比赛顺序已经定好。 现在让你将这些选手分成 $2$ 队，使选手尽可能晚地碰到同队的选手。 输出最优方案下第一次有选手碰到同队的的选手的比赛序号。

第一行，一个正整数 $N$，表示有 $N$ 个选手； 第二行，一个正整数 $M$，表示有 $M$ 场比赛； 接下来 $M$ 行，每行两个正整数 $A_i$ 和 $B_i$，表示序号为 $i$ 的比赛参与的选手是序号为 $A_i$ 和 $B_i$ 的两位选手。

一行，一个正整数，表示最优分队方案下第一次有选手碰到同队的的选手的比赛序号。

**【样例解释 #1】** $[1,3,5]$ 一队， $[2,4]$ 一队。 可以证明这是最优方案。 **【数据范围】** 对于 $100\%$ 的数据，$1\le A_i,B_i\le N\le 10^5$，$1\le M\le 3\times 10^5$。 **【来源】** 本题分值按 COCI 原题设置，满分 $100$。 题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T3 SUMO**_。