스모

엄격한 금식과 수행으로 알려진 일본의 한 사찰에서 스모를 맡은 책임자가 소속 선수 $N$명을 모아 훈련 경기를 열기로 했다. 책임자는 총 $M$번의 경기 순서와 각 경기에 나설 두 선수를 미리 정해 두었다.

첫 경기 직전, 책임자는 선수를 두 팀으로 나누면 훈련을 조금 더 흥미롭게 만들 수 있다는 것을 깨달았다. 모든 경기가 서로 다른 팀끼리 맞붙는 대결이 되도록 나누고 싶지만, 경기 순서는 선(禪)의 어떤 이유로도 바꿀 수 없고 이 순서로는 그런 편성이 존재하지 않는다. 남은 방법은 하나뿐이다. 같은 팀 선수끼리 맞붙는 경기가 최대한 늦게 나오도록 두 팀을 나누는 것이다.

경기 순서가 주어질 때, 두 팀을 가장 잘 나눴을 경우 같은 팀 선수끼리 처음으로 맞붙는 경기가 몇 번째인지 구하라. 주어지는 모든 입력에서 그런 경기는 반드시 발생한다.

첫째 줄에 선수의 수 $N$이 주어진다. ($1 \le N \le 100\,000$) 선수는 $1$번부터 $N$번까지 번호가 붙어 있다.

둘째 줄에 경기의 수 $M$이 주어진다. ($1 \le M \le 300\,000$)

이어지는 $M$개의 줄에는 경기가 열리는 순서대로 각 경기에 나설 두 선수의 번호가 주어진다. 각 줄에는 $[1, N]$ 범위의 서로 다른 두 정수가 있다.

같은 팀 선수끼리 처음으로 맞붙는 경기의 번호를 한 줄에 출력한다. 이 번호는 $1$ 이상 $M$ 이하이다.