anniversary 思考题

Very Easy Problem

Wow! OBCYSIO has reached 50 episodes! Let's celebrate using a very popular and easy problem.

Hikari and Ninetail are playing a game on an undirected graph of N nodes and M edges. They move in turns, with Hikari being the first one. For each turn, the player must find a cycle in the graph and remove one edge on it (she gets to choose which one she removes). The game continues until the graph has no cycle. The player who cuts the last edge wins.

It is not guaranteed that the graph is connected. It is also possible for it to have self-loops or multiple edges between the same pair of nodes.

A cycle is a sequence of distinct node C_i that (C_i,C_{i+1})\in E with \forall 1\leq i\leq |C|-1 and (C_{|C|},C_{1})\in E

Given the graph, your task is to find out who will win if both players are playing optimally.