Notice that the locked boxes form a directed graph. An edge from box ~u~ to box ~v~ means that box ~v~ can be opened after obtaining a key from box ~u~. Since only one key is directly required to open any given box, we simply need to find the shortest path to the to box with the treasure. This can be computed using Dijkstra's algorithm once we have constructed the graph.

The weight of the edge from box ~u~ to box ~v~ is equal to the distance between the rooms that they are located in. All that is left is to compute these distances.

Subtask 1

It is sufficient to perform a BFS or DFS to find the distances.

Subtask 2

Since the rooms are arranged in a tree, we can compute distances using LCA. More specifically, we can root the tree arbitrarily and compute distances from the root to each node. Define ~d_x~ as the distance from the root to node ~x~. The distance between two nodes ~x~ and ~y~ can be computed as ~d_x + d_y - 2d_{LCA(x, y)}~.