CF1363C Game On Leaves

Ayush and Ashish play a game on an unrooted tree consisting of $ n $ nodes numbered $ 1 $ to $ n $ . Players make the following move in turns: - Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to $ 1 $ . A tree is a connected undirected graph without cycles. There is a special node numbered $ x $ . The player who removes this node wins the game. Ayush moves first. Determine the winner of the game if each player plays optimally.

N/A

N/A

For the $ 1 $ st test case, Ayush can only remove node $ 2 $ or $ 3 $ , after which node $ 1 $ becomes a leaf node and Ashish can remove it in his turn. For the $ 2 $ nd test case, Ayush can remove node $ 2 $ in the first move itself.