Cat and Mouse

A cat and mouse are playing a turn-based game on an undirected graph.
• The graph is represented as an adjacency list:
graph[a] contains all nodes b such that there is an edge between a and b.
• The mouse starts at node 1 and moves first.
• The cat starts at node 2 and moves second.
• There is a hole at node 0, which represents a safe zone for the mouse.
________________________________________
🧩 Game Rules
1. On a player’s turn, they must move to one of the neighboring nodes connected to their current position.
2. The cat cannot move to the hole (node 0).
3. The game ends in one of three ways:
o If the mouse reaches node 0, the mouse wins.
o If the cat and mouse are on the same node, the cat wins.
o If the same position repeats (same player’s turn, same positions), the game is a draw.
________________________________________
🏁 Return
• 1 → if the mouse wins
• 2 → if the cat wins
• 0 → if the game ends in a draw
Both players play optimally to maximize their chances of winning.