贪吃虫

题目背景

我们都知道一个很著名的游戏——贪吃蛇。它的一大特点是当前一个食物被吃掉后，后一个食物才会出现。今天我们要做的另一个游戏——贪吃虫也很类似。

题目描述

贪吃虫有 $k$ 条，在一棵有 $n$ 个节点的树上，每只虫子都在不同的节点上。第一个食物到来时，所有的 $k$ 只虫会从它们当前的位置出发，前往食物的位置。它们的移动遵循如下规则：

• 这棵树上的任何两个节点之间有且仅有一条路，所有的贪吃虫沿着唯一的路径前往食物所在的位置；
• 如果有一只贪吃虫到达了食物所在的位置，食物马上就被吃掉了；
• 如果有另外一只贪吃虫在某一只贪吃虫通往食物的道路上，那么距离食物较远的那只虫子会停止移动，停留在当前的节点上；
• 如果有多只虫子尝试进入同一个节点，只有编号最小的虫子能够到达，其它的贪吃虫停留在它们当前的位置上；
• 吃掉食物的那只虫子会停留在食物的位置上；
• 食物被吃掉之后会出现在树上的另外一个节点上。这时所有的贪吃虫会重新出发，尝试再一次吃掉食物。为了简化过程，我们假设从一个节点移动到相邻的节点需要花费一个单位时间。

输入格式

第 $1$ 行一个整数 $n$，表示树上的节点个数。

第 $2$ 至 $N$ 行，第 $i+1$ 行包含了一个两个整数 $:A_i,B_i$，表示从节点 $A_i$ 到节点 $B_i$ 有一条边直接相连。

第 $N+1$ 行有一个整数 $k$，表示树上贪吃虫的个数。

第 $N+2$ 至 $N+1+k$ 行，第 $N+1+i$ 行有一个整数 $P_i$，表示第 $i$ 只贪吃虫开始时的位置，任何两只贪吃虫的初始位置不相同。

第 $N+2+k$ 行：有一个整数 $h$，表示食物一共在树上出现了多少次。

接下来的 $h$ 行，每行一个整数，表示食物依次出现的位置。

输出格式

输出一共包含 $k$ 行，第 $i$ 行有两个整数 $C_i$ 和 $D_i$。分别表示第 $i$ 只贪吃虫最终停留的位置和这只贪吃虫吃到食物的次数。

样例 #1

样例输入 #1

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

样例输出 #1

1 0
4 2

提示

数据范围及约定

对于全部数据，$1 \le n \le 5000$，$1 \le k \le 1000$，$k \le n$，$1 \le h \le 500$。