Description

There are $k$ worms on a tree with $n$ nodes, and each worm is on a different node. When the first food appears, all $k$ worms start from their current positions and move toward the food. Their movement follows these rules:

• Between any two nodes on the tree there is exactly one path, and all worms move along the unique path toward the food.
• As soon as a worm reaches the food’s node, the food is immediately eaten.
• If there is another worm on a worm’s path to the food, the worm that is farther from the food stops moving and stays at its current node.
• If multiple worms attempt to enter the same node at the same time, only the worm with the smallest index can enter; the others remain at their current nodes.
• The worm that eats the food stays at the food’s node.
• After the food is eaten, it will appear at another node on the tree. At that moment, all worms start again from their current positions and try to eat the food. To simplify, moving from a node to an adjacent node takes one unit of time.

Input Format

• The first line contains an integer $n$, the number of nodes in the tree.
• The next $n - 1$ lines: line $i + 1$ contains two integers $A_i, B_i$ ($1 \le i \le n - 1$), indicating there is an edge between nodes $A_i$ and $B_i$.
• The next line contains an integer $k$, the number of worms on the tree.
• The next $k$ lines: line $n + 1 + i$ contains an integer $P_i$, the initial position of the $i$-th worm; no two worms share the same initial position.
• The next line contains an integer $h$, the number of times the food appears.
• The next $h$ lines: each line contains one integer, the position where the food appears, in order.

Output Format

Output $k$ lines. On the $i$-th line, print two integers $C_i$ and $D_i$, denoting the final position of the $i$-th worm and the number of times this worm eats the food, respectively.

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

1 0
4 2

Hint

Constraints

For all testdata: $1 \le n \le 5000$, $1 \le k \le 1000$, $k \le n$, $1 \le h \le 500$.

Translated by ChatGPT 5