在一座以严格斋戒和苦行生活闻名的日本寺庙里，相扑部门的主管决定为他的 $N$ 名选手组织一次训练赛。他确定了 $M$ 场比赛的精确顺序以及每场比赛的参赛者（每场比赛有两名选手对决）。

就在比赛开始前，主管意识到他可以稍微增加一些趣味性！他可以将选手们分成两支队伍，使得在每场比赛中，只有来自不同队伍的选手进行对决。由于比赛日程已经制定好，且不满足这一条件，而由于某种禅宗原因我们又不能修改日程，主管只剩下一种选择：将选手分成两支队伍，使得同一队伍的选手之间发生对决的比赛尽可能晚地出现。

请帮助主管！对于给定的比赛日程，在以最佳方式划分队伍的前提下，确定第一场不得不让同一队伍的选手进行对决的比赛的编号（从 $1$ 开始），使得这场比赛尽可能晚地发生。在所有的测试数据中，这样的比赛一定会出现。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)，表示选手的数量。选手用 $1$ 到 $N$ 的数字进行标记。

第二行包含一个整数 $M$ ($1 \le M \le 300\,000$)，表示比赛的数量。

接下来的 $M$ 行按比赛进行的顺序给出每场比赛。每行包含两个介于 $[1, N]$ 之间的不同整数，表示将要进行对决的两名选手的编号。

输出格式

输出第一行且仅一行，包含所求比赛的编号（从 $1$ 到 $M$）。

样例

输入样例 1

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

输出样例 1

5

输入样例 2

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

输出样例 2

6