To solve the first subtask with dynamic programming with ~\mathcal O(n^2)~ states and ~\mathcal O(n)~ transitions, see this link.

The main insight in the second subtask is that Paula certainly wins if the path length between the starting positions of Paula and Marin is even, and Marin if the length is odd. The reason for this is that the player with the right parity can take on the role of a hunter, approaching the opponent with every move. The hunter will then drive the opponent into a leaf and win. Therefore, for the second subtask it was enough to find the path length between ~a~ and ~b~ with depth-first search and print the winner depending on the parity. The complexity is ~\mathcal O(n)~.

In the last subtask, the above insight is partially preserved. It is no longer true that the player with the right parity will surely win, but they can always either win or draw. The hunter will again hunt the opponent, but this time, due to the possible edges that are impassable to the hunter, the opponent may be able to escape and thus secure a draw. Before embarking on the analysis of how to escape, let us mention special cases when Paula cannot make the first move and when Marin has only blue edges. In the first case Marin wins, and in the second case Paula wins.

Barring the above special cases, Paula and Marin can make their moves. Hence, the game will then end either with the hunter catching the opponent, or the opponent managing to escape and secure a draw.

Note that if there is an edge such that both its vertices are accessible to the fleeing player, where we consider a node that can be reached from the starting point, and no vertex of that edge is accessible to the hunter, then it's a draw. If such an edge does not exist, the hunter wins. It remains to check whether there is such an edge.

We will start depth-first search from the initial position of the hunter, and for each vertex available to the hunter, write down the initial distance.

After that, we start depth-first search from the fleeing player, with the additional condition that we expand into a vertex only if the distance we from the fleeing player to it is less than the initial distance of the hunter to that vertex, that is, if we can reach that node without colliding with hunter.

If during this search we encounter an edge that leads us to a vertex to which we can expand, and if the current vertex, as well as the vertex to which we expand, are not available to the hunter, it is a draw because we found an edge on which the fleeing player can oscillate indefinitely. The total complexity is ~\mathcal O(n)~.