At the end of the game, \(G\) will consist of two connected components that are complete graphs. Let \(n\) and \(N-n\) be the sizes of these components containing Vertex \(1\) and Vertex \(N\), respectively. Then, there are \(N(N-1)/2 - n(N-n)\) edges in total. Since the players alternately take turns, the first player wins if \(N(N-1)/2 - n(N-n) - M\) is odd, and the second player wins if it is even.

Here, if \(N\) is odd, one of \(n\) and \(N-n\) must be even, so the parity of \(N(N-1)/2 - n(N-n) - M\) does not depend on the two players’ moves. Thus, we just need to check the parity of \(N(N-1)/2 - M\) in this case.

If \(N\) is even, the parity of \(N(N-1)/2 - n(N-n) - M\) does depend on the parities of \(n\) and \(N-n\). Let \(x\) and \(y\) be the sizes of the components containing Vertex \(1\) and Vertex \(N\), respectively, at the beginning of the game. We will show the following: if \(x\) and \(y\) have different parities, the first player always wins; otherwise, the first player wins if \(N(N-1)/2 - xy - M\) is odd, and the second player wins if it is even.

If \(x\) and \(y\) have different parities, the first player can play his first move so that the parities of \(x\) and \(y\) change in his favor. Then, whatever moves the second player play, the first player can always play a move to negate the change in the parities of \(x\) and \(y\), or a move that does not affect the parities, leading to his victory.

The case in which \(x\) and \(y\) have the same parities is almost the same as the case above. If \(N(N-1)/2 - xy - M\) is odd at the beginning of the game, whatever the second player does, the first player can always negate the change in the parities or avoid affecting the parities, leading to his victory. If \(N(N-1)/2 - xy - M\) is even at the beginning, the second player can do almost the same to guarantee his victory.

We can check if these conditions hold in \(O(N+M)\) time, which is fast enough.