Problem - Cat and Mouse (Part 1)

The problem gives you a graph where the cat and mouse take turns moving. The state is (mouse position, cat position, whose turn). The mouse starts at vertex $1$, the cat at vertex $2$, and the food is at vertex $0$.

The cat cannot move to vertex $0$. You need to determine the outcome when both players play perfectly. This is a game on a product graph: the original graph crossed with itself. The state space has $O(n^2)$ states times $2$ for whose turn it is.