For the first subtask, notice that if ~a_v = v~ as soon as Marin enters room ~v~ the game ends. Also if ~a_v~ is adjacent to ~v~ Marin can first go to room ~v~ and in the next move enter room ~a_v~ and the game ends. In the only remaining case it is enough to check only the last step of the game, if in his last move Marin goes from room ~u~ to room ~v~ we need to check if Luka can get from room ~a_u~ to room ~a_v~ without passing through room ~v~. For that it is enough to remove vertex ~v~ from the graph and check if ~a_u~ and ~a_v~ are connected with a standard dfs algorithm. Now that we know all possible last moves we can easily calculate how many moves are necessary to end the game from each starting room using bfs. Since there are ~2m~ possible last moves (one for each direction of each edge), and dfs and bfs run in ~\mathcal{O}(n+m)~ time complexity, the total time complexity of this approach is ~\mathcal{O}(m(n+m))~.

In the second subtask, the graph is a tree so to check if ~a_u~ is connected to ~a_v~ after removing vertex ~v~ we can use LCA which has a time complexity of ~\mathcal{O}(\log n)~.

Consider ~a_v \ne v~ nor ~a_v~ is adjacent to ~v~, the game can only end in articulation points. Furthermore, since for each articulation point it is fairly easy to construct a hiding strategy for which the game can end in that vertex, we conclude that the second part of the third subtask is equivalent to: "There are at most ~5~ articulation points." We can find articulation points using dfs spanning tree in time complexity of ~\mathcal{O}(n+m)~. Since there are at most ~5~ of them, for each articulation point ~v~ we can check if ~a_v~ is connected to ~a_u~ with dfs similar to the first subtask.

For the complete solution, we need to check if vertices ~a_v~ and ~a_u~ are connected after removing vertex ~v~ faster. In dfs spanning tree consider times of entry for each vertex in the same connected component with respect to some articulation point ~v~. It holds that times of entry of every vertex in some connected component that is not connected to the root of dfs spanning tree form a continuous interval. The claim follows from the fact that dfs visits all nodes from some connected component before recursively backtracking back to the articulation point. Now we can determine in which interval some node belongs using binary search, and if it doesn't belong to any interval we know it is in the component connected to the root of dfs spanning tree. Time complexity of such an approach is ~\mathcal{O}(n + m \log n)~. For implementation details refer to the attached source code.

In the attached source codes there will also be an alternative solution to this problem.

(Note that the source codes are available on the COCI website)