N명의 선수들이 탁구 리그를 벌인다. 리그의 스케줄은 총 M개의 경기로 이루어져 있으며, 1:1로 이루어진다. 주최자인 당신은 선수들의 경쟁심을 도취시키기 위해서 A팀, B팀으로 나누어서 리그를 진행하려고 한다. 이때 각 경기는 되도록 A팀 선수와 B팀 선수끼리 이루어져야 한다. 허나, 이미 일정이 다 짜인 상태에서, 어쩔 수 없이 같은 팀의 선수끼리 경기하는 경우가 있다. 따라서 당신은 같은 팀 선수끼리의 대결은 최대한 늦추고 싶다. 스케줄이 주어질 때 조건을 만족하는 팀 분배 방법을 구하는 프로그램을 작성하여라.

입력 형식

• 첫 번째 줄에는 선수의 수 N이 주어지고
• 두 번째 줄에는 경기의 수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)
• 세 번째 줄부터 M개의 줄에는 리그의 각 경기에 참여하는 두 선수의 번호가 주어진다. 선수의 번호는 1과 N 사이의 자연수이다.

출력 형식

입력 예 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

Just moments before the competition, the Head realised he could easily stir things up a bit! He could divide his fighters into two teams so that only fighters of different teams face each other in each fight. Since the fighting schedule has already been made and it doesn't meet this condition, and we mustn't change it for whatever zen reason there is, the Head is left with only one option. That is to divide the fighters into two teams so that the fighters from the same team face each other in a fight as late as possible.

Help the Head! For a given fighting schedule, determine the ordinal number of the first fight where two fighters from the same team have to face each other, under the condition that we divide them in the best possible way, so that the required fight takes place as late as possible. In all test data, such fight will definitely occur.

INPUT

• The first line of input contains the integer N (1 ≤ N ≤ 100 000), the number of fighters. The fighters are marked with numbers from 1 to N.
• The second line of input contains the integer M (1 ≤ M ≤ 300 000), the number of fights.
• Each of the following M lines contains fights in the order which they must take place. Each line contains two different integers from the interval [1, N]: the labels of fighters who are going to face each other.

OUTPUT

SAMPLE TESTS

input

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

output

5

input

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

output
6

출처:coci/2013-2014/contest4
번역:functionx