## 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:

- 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).

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

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

### Output for sample input

5 2
2 2
7 1

*Krzysztof Lorys, adapted by P. Rudnicki*

ACPC 2005