Problem H: Ants, Aphids and a Ladybug

If you are searching for ladybugs, the best place to look is near ants. The ants suck sweet honeydew from aphids and therefore, where there are ants, there must be aphids. Where there are aphids, there are more likely to be ladybugs. Ants defend aphids against ladybugs --- for which aphids are a much sought for delicacy.

An old tree near the anthill serves as an aphid farm. On the old tree, branches connect the forks (spaces where two or more branches meet) and leaves where the aphids feed. There are k ant-guards (numbered from 1 to k) working on the farm. A ladybug hunting aphids lands on the places where aphids feed, i.e. on leaves or forks. When a ladybug lands on the tree, the guard-ants set off in her direction in order to chase her away. They comply with the following rules: 

The ladybug is stubborn and lands on the tree again, and then the ant-guards set off again trying to chase the intruder away. In order to simplify the problem we assume that for each ant it takes a unit of time to walk between two neighboring forks or a fork and a leaf (2 leaves cannot be neighbors).

The input file contains multiple test cases. Each test case starts with an integer n, the number of leaves and forks in the tree, 1<=n<=5000. We assume that leaves and forks are numbered from 1 to n. Each of the following n-1 lines describes tree branches; each branch is described by two integers a and b, meaning that the branch connects forks or leaves labeled a and b. In the (n+1)-st line there is one integer k, 1<=k<=1000 and k<=n; k is the number of ants that guard the tree. There is one positive integer (not greater than n) in each of the following k lines. The integer written in the (n+1+i)-th line is the start position of the  i-th ant. There is no fork or leaf in the tree occupied by more than one ant. The line n+k+2 contains one integer l, 1<=l<=500, l saying how many times a ladybug lands on the tree. Each of the following l lines contains one positive integer (not greater than n). These numbers define a sequence of tree places in which the ladybug lands. Input is terminated by the case with n equal to 0.

Your program should output k lines for each test case. In the i-th line for a case there should be two integers separated by a single space --- the final position of the i-th ant (number of a fork or a leaf) and the number of times the i-th ant chased the ladybug away.

Sample input

1 2
1 3
2 4
2 5
3 6 
3 7
5 8

Output for sample input

5 2
2 2
7 1

Krzysztof Lorys, adapted by P. Rudnicki
ACPC 2005