개미와 무당벌레

개미는 진딧물을 기른다. 진딧물이 내놓는 달콤한 감로를 개미가 받아먹기 때문에, 개미들은 진딧물의 가장 큰 천적인 무당벌레로부터 진딧물을 지킨다. 개미집 옆의 나무에는 이런 진딧물 무리가 살면서 나무의 잎과 가지가 갈라지는 지점을 갉아먹는다.

나무에는 잎과 분기점을 합쳐 $n$개의 자리가 있으며 $1$번부터 $n$번까지 번호가 매겨져 있다. 이 자리들은 $n-1$개의 가지로 이어져 있어, 어떤 두 자리 사이에도 단순 경로가 정확히 하나뿐이다. 나무는 $1$번부터 $k$번까지 번호가 붙은 $k$마리의 경비 개미가 지킨다. 각 개미는 서로 다른 자리에 서 있으며, 한 자리에 두 마리 이상의 개미가 있는 경우는 없다.

무당벌레가 어떤 자리에 내려앉으면 개미들이 무당벌레를 쫓아내려 한다. 모든 개미의 속도는 같아서, 가지 하나를 건너는 데 시간 한 단위가 걸린다. 무당벌레가 한 번 내려앉을 때마다 다음 규칙에 따라 상황이 정리된다.

• 무당벌레가 앉은 자리에 이미 개미가 서 있으면, 무당벌레는 곧바로 날아오르고 그 개미가 무당벌레를 쫓아낸 것으로 센다. 이때 어떤 개미도 움직이지 않는다.
• 그렇지 않으면 각 개미는 자기 자리에서 무당벌레가 앉은 자리로 가는 유일한 경로를 따라 나아간다. 단, 그 경로 위(자기 자리는 제외) 어디에도 다른 개미가 없을 때에만 출발하며, 이렇게 막힌 개미는 전혀 움직이지 않고 제자리에 머문다.
• 출발한 개미들은 시간 한 단위마다 가지 하나씩 동시에 나아간다.
• 두 마리 이상의 개미가 같은 순간에 같은 자리로 들어가려 하면, 그중 번호가 가장 작은 개미만 그 자리에 들어가고 나머지는 제자리에 멈춰 더는 나아가지 않는다.
• 어떤 개미가 무당벌레가 앉은 자리에 도착하는 순간 무당벌레를 쫓아내고 그 자리에 머문다. 그 순간 다른 모든 개미도 지금 있는 자리에 멈춘다.

무당벌레는 고집이 세서 몇 번이고 다시 나무에 내려앉는다. 내려앉을 때마다 개미들은 지금 서 있는 자리에서 새로 출발한다.

나무의 구조, 개미들의 처음 자리, 그리고 무당벌레가 차례로 내려앉는 자리가 주어질 때, 각 개미의 마지막 자리와 그 개미가 무당벌레를 쫓아낸 횟수를 구하는 프로그램을 작성하라.

첫째 줄에 자리의 개수 $n$ ($1 \le n \le 5000$)이 주어진다. 다음 $n-1$개의 줄에는 각각 두 정수 $a$와 $b$ ($1 \le a, b \le n$)가 주어지는데, 이는 자리 $a$와 자리 $b$를 잇는 가지가 있다는 뜻이다.

그다음 줄에는 개미의 수 $k$ ($1 \le k \le 1000$, $k \le n$)가 주어진다. 이어지는 $k$개의 줄에는 각각 $[1, n]$ 범위의 정수 하나가 주어지며, 이는 $i$번째 개미의 처음 자리이다. 모든 개미의 처음 자리는 서로 다르다.

그다음 줄에는 무당벌레가 내려앉는 횟수 $l$ ($1 \le l \le 500$)이 주어진다. 이어지는 $l$개의 줄에는 각각 $[1, n]$ 범위의 정수 하나가, 무당벌레가 내려앉는 순서대로 주어진다.

$k$개의 줄을 출력한다. $i$번째 줄에는 두 정수를 공백 하나로 구분하여 출력하는데, 이는 $i$번째 개미의 마지막 자리와 그 개미가 무당벌레를 쫓아낸 횟수이다.

아래 그림은 첫 번째 예제의 나무를 나타낸다.

이 예제에서 가지는 $1-2$, $1-3$, $2-4$이고, 개미 $1$은 자리 $1$에서, 개미 $2$는 자리 $2$에서 출발한다. 무당벌레가 먼저 자리 $2$에 내려앉으면, 개미 $2$가 이미 그 자리에 있으므로 곧바로 무당벌레를 쫓아내고 아무도 움직이지 않는다. 이어서 자리 $4$에 내려앉으면, 개미 $1$(자리 $1$)에서 자리 $4$로 가는 경로가 개미 $2$가 서 있는 자리 $2$를 지나므로 개미 $1$은 제자리에 머물고, 개미 $2$가 자리 $2$에서 자리 $4$로 한 칸 이동하여 다시 무당벌레를 쫓아낸다. 결국 개미 $1$은 자리 $1$에 그대로 있고 쫓아낸 횟수는 $0$번, 개미 $2$는 자리 $4$에 있고 쫓아낸 횟수는 $2$번이다.