Determine the outcome of a two-player turn-based chase on a graph where each player moves optimally.
You are given a finite graph and two players: a mouse and a cat. The mouse starts at one node, the cat starts at another node, and the players alternate turns. On each turn, the active player must move along one edge to a neighboring node. Both players play optimally.
The mouse wants to reach a designated target node before being caught. The cat wants to land on the mouse's node to catch it, or otherwise prevent the mouse from winning. The game may also end in a draw if neither side can force a win.
Your task is to determine the final outcome of the game from the given starting positions.
This is a state-based game on a graph: the result depends not only on the current positions, but also on whose turn it is and how both players can respond in the future.
Example 1
Input
graph = [[1,2],[0,2],[0,1]], mouseStart = 0, catStart = 2
Output
draw
Explanation
On this triangle graph, neither side can force a decisive result from every optimal line of play, so the game can repeat states and end in a draw.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.