Greedy Worms

There are \(k\) worms on a tree with \(n\) nodes, each located at a distinct node. When food appears at a node \(f\), all worms start moving toward \(f\) along the unique simple path connecting their current position and \(f\). The movement follows these rules:

• For any two nodes there is exactly one simple path.
• If a worm reaches \(f\), the food is immediately eaten and the process stops for this round.
• If, along a worm's path to \(f\), there is another worm positioned closer to \(f\) (i.e. on the unique path between its current node and \(f\)), then the farther worm stops moving and remains at its current node.
• If several worms try to enter the same node at the same time, only the worm with the smallest identifier succeeds; the others stay where they are.
• The worm that eats the food stays at \(f\).
• After the food is eaten, it appears at a new node and the worms start a new round of movement (with their positions updated from the previous round).
• Moving from one node to an adjacent node takes one unit of time.

Your task is to simulate the process over \(q\) food events. For each event, you are given the node \(f\) where the food appears. Initially, the worms are at specified positions. For every food event, determine which worm reaches the food (i.e. eats it) and how long (in time units) it took. Note that if a worm is blocked by another worm on its path, it never moves during that round (its position remains unchanged).

Determining the Winner

For each food event, let the current position of worm \(i\) be \(p_i\) and let \(d_i=\text{dist}(p_i, f)\) be the distance from \(p_i\) to \(f\). A worm \(i\) is blocked if there exists another worm \(j\) (\(j\neq i\)) with \(d_j < d_i\) such that \(p_j\) lies on the unique path from \(p_i\) to \(f\) (i.e. \(\text{dist}(p_i, f)=\text{dist}(p_i, p_j)+\text{dist}(p_j, f)\)). Only unblocked worms can move. Among these, the worm with the smallest \(d_i\) will reach the food first; in case of a tie, the worm with the smallest identifier wins.

After a worm reaches \(f\) (and eats the food), its position is updated to \(f\); all other worms remain at their positions.

inputFormat

The input consists of:

• One line with three integers \(n\), \(k\), and \(q\) \( (1 \leq k \leq n)\): the number of nodes in the tree, the number of worms, and the number of food events.
• \(n-1\) lines each with two integers \(u\) and \(v\), denoting an edge between nodes \(u\) and \(v\).
• One line with \(k\) distinct integers, where the \(i\)th integer is the initial node of worm \(i\) (worms are identified from 1 to \(k\)).
• \(q\) lines, each with a single integer \(f\): the node where the food appears for that event.

outputFormat

For each food event, output a line with two integers: the identifier of the worm that eats the food and the time taken (number of moves) for that worm to reach the food.

sample

4 2 2
1 2
2 3
3 4
4 2
1
3

2 1
1 1