题目描述

有 $N$ 个选手参加 $M$ 场 $1$ 对 $1$ 的比赛，比赛顺序已经定好。

现在让你将这些选手分成 $2$ 队，使选手尽可能晚地碰到同队的选手。

输出最优方案下第一次有选手碰到同队的的选手的比赛序号。

输入格式

第一行，一个正整数 $N$，表示有 $N$ 个选手；

第二行，一个正整数 $M$，表示有 $M$ 场比赛；

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

输出格式

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

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

提示

【样例解释 #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 T3 SUMO。