Delayed Intra-Team Collision

There are \(N\) players participating in \(M\) 1-on-1 matches, where the order of the matches is predetermined. You are allowed to split the players into two teams. Your goal is to postpone the event when two players from the same team meet for as long as possible.

Formally, the first \(x\) matches (in the given order) can be arranged so that in every match the two players belong to different teams. However, no matter how you assign the teams, match number \(x+1\) will force two players from the same team to be paired. If you are able to avoid any intra-team collision in all \(M\) matches, then output \(M+1\). Determine the match index of the first collision under an optimal assignment.

inputFormat

The first line contains two integers \(N\) and \(M\) (1 ≤ N, M). The next \(M\) lines each contain two integers \(a\) and \(b\) (\(1 ≤ a, b ≤ N\)), representing the two players participating in that match in the given order.

outputFormat

Output a single integer: the match index when the first intra-team collision occurs under the optimal team assignment. If all matches can be arranged with players from different teams, output \(M+1\).

sample

3 3
1 2
2 3
1 3

3