题目描述
有 $N$ 个选手参加 $M$ 场 $1$ 对 $1$ 的比赛，比赛顺序已经定好。
现在让你将这些选手分成 $2$ 队，使选手尽可能晚地碰到同队的选手。
输出最优方案下第一次有选手碰到同队的的选手的比赛序号。
输入格式
第一行，一个正整数 $N$，表示有 $N$ 个选手；
第二行，一个正整数 $M$，表示有 $M$ 场比赛；
接下来 $M$ 行，每行两个正整数 $A_i$ 和 $B_i$，表示序号为 $i$ 的比赛参与的选手是序号为 $A_i$ 和 $B_i$ 的两位选手。
输出格式
一行，一个正整数，表示最优分队方案下第一次有选手碰到同队的的选手的比赛序号。
样例输入 #1
5
5
1 2
2 3
3 4
4 5
5 1
样例输入 #2
6
8
1 2
3 4
5 6
1 3
1 6
4 5
2 4
2 6
提示
对于 $100\%$ 的数据，$1\le A_i,B_i\le N\le 10^5$，$1\le M\le 3\times 10^5$。