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 (num- bered 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: • There is exactly one way for an ant to go from one fork or leaf in the tree to another fork or leaf without ever turning back. Upon the ladybug’s landing, all of the ant-guards simultaneously start going along such a route to the place where the ladybug landed. • If there is an ant in the place of the ladybug’s landing, the ladybug takes off immediately. • If at any time an ant rushing towards the ladybug spots another ant anywhere ahead on its route, the ant stops and remains in its current position, yielding to the ant that is farther ahead. • If two or more ants try to reach the same fork of the tree at the same time, only one does so – the one with the smallest id number. The other ants trying to reach the same fork remain in their places. • An ant which gets to the place of ladybug’s landing chases it away and remains in this place. 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). Input 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
2/2 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. Output 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 8 12 13 24 25 36 37 58 3 1 2 6 5 2 4 5 8 7 0 Sample Output 52 22 71