Police and a thief play on a connected undirected graph with n nodes and m edges. The police starts at node a, the thief at node b. The police moves first, then they alternate turns. On each turn, a player may move along exactly one edge to an adjacent node, or stay in place. The police wins if they occupy the same node as the thief at any time after the police's move. The thief wins if they can evade capture indefinitely. Both play optimally. Determine whether the police can catch the thief.

The graph may contain cycles. Unlike a tree, the thief can use cycles to escape.