Graph Game Winner

You are given an undirected graph with n vertices and m edges. Two players play a game on the graph by selecting vertices such that the chosen vertices form an independent set. The twist is that the outcome of the game (i.e. who is guaranteed a win) is determined by the structure of the graph.

The procedure is as follows:

• First, the graph is separated into its connected components.
• For each connected component, if the component is non-bipartite (i.e. it contains an odd cycle), the winner is immediately declared as Player 1.
• If a component is bipartite, compute two values: the number of vertices in the component, vertex_count, and the maximum degree among the vertices in that component, degree_count. For that component, calculate a value using the formula:

\( (vertex\_count \bmod 2) \oplus (degree\_count \bmod 2) \)

Here, \( \oplus \) denotes the bitwise XOR. Then compute the XOR sum (\( xor\_grundy \)) over all such bipartite components. If \( xor\_grundy = 0 \), then Player 2 wins; otherwise, Player 1 wins.

Your task is to implement a program which, given the graph, determines and prints the winning player to standard output.

inputFormat

The first line of input contains two space-separated integers n and m, representing the number of vertices and edges respectively. This is followed by m lines, each containing two space-separated integers u and v that describe an undirected edge between vertices u and v.

outputFormat

Output a single line containing either Player 1 or Player 2, indicating the winner as computed by the above rules.

3 2
1 2
2 3

Player 1