Cycle Game

The cycle game is played by two players who take turns, with the first player taking the odd-numbered turns and the second player taking the even-numbered turns. At the start of the game, n points on the plane are given, numbered uniquely from 0 to n − 1, and no three of them lie on the same line. On each turn, a player chooses two points and draws the line segment connecting them. A segment that was drawn before cannot be drawn again, but it may cross other segments that have already been drawn. The game ends the moment a cycle is completed for the first time. A cycle C is a subset of the segments drawn by the players that satisfies the following condition.

Starting from one endpoint of any segment in C, one can traverse every segment exactly once and return to the starting point.

The problem is that as more segments are drawn, it becomes hard to tell whether a cycle has been completed, so the game may continue even after a cycle has already been completed. To fix this, given the progress of the game, write a program that determines on which turn a cycle was completed, or whether the game is still in progress.

Given the number of points n and the progress of the game up to turn m, write a program that determines whether a cycle has been completed and, if so, prints the number of the turn on which a cycle was first completed.

The input uses standard input. The first line gives the integer 3 ≤ n ≤ 500,000, the number of points, and the integer 3 ≤ m ≤ 1,000,000, the number of turns played. The n points used in the game are numbered uniquely from 0 to n − 1, and no three of them lie on the same line. The following m lines each give the numbers of the two points chosen by the player on the i-th turn (1 ≤ i ≤ m).

The output uses standard output. For the case given as input, if the game has already ended by turn m, print as a positive integer the number of the turn on which a cycle was first formed; if the game has not ended even after all m turns are processed, print 0.