## Ants and the ladybug

## POI VIII Stage 2 Problem 4## Ants and the ladybug
As we all know ants are able to raise aphides. Aphides produce sweet honey dew, which is drank
by ants. Ants defend aphides against the bitterest enemies of theirs - ladybugs. On the tree near to the anthill there lives
such culture of aphides. Aphides feed on leaves and ramifications of the tree.
There are - between any two chosen places on the tree (leaves or ramifications) there is exactly one way to go without turning back - each of the ants starts going along such route to the place of ladybug's landing,
- if there is an ant in the place of the ladybug's landing, the ladybug takes off immediately,
- if there is another ant on the route to the ladybug landing place, then the ant that is farther from the ladybug stops its wandering and remains on its current position,
- if two or more ants try to get to the same ramification of the tree, only one reaches it - the one with the least number, the others stay on their positions (leaves or ramifications),
- an ant which gets to the place of ladybug's landing chases it away and stays on this position.
The ladybug is stubborn and lands on the tree again. Then ants set off again trying to chase away the intruder. In order to simplify we assume that getting through one branch connecting a leaf with a ramification or connecting two ramifications takes a unit of time. ## TaskWrite a program which: - reads from the input file MRO.IN the description of the tree, the start positions of ants, and places where the ladybug lands,
- for each ant finds its final position and number of times this ant chased the ladybug away,
- writes the result into the output file MRO.OUT.
## InputIn the first line of the text file MRO.OUT there is one integern, equal to the number of leaves and ramifications
on the tree, 1<=n<=5000. We assume that leaves and ramifications are numbered from 1 to
n. Each of the following n-1 lines describes a branch --- a
description consist of two integers
a and b, it means that a given branch connects places
a and b of the tree. The branches allow to get from one place to the another. In the
(n+1)-st line there is one integer k, 1<=k<=1000 and k<=n;
k is equal to number of ants that guard the tree. In each of the following
k lines one positive integer (not grater than n) is written. An integer written in
(n+1+i)-th line is a start position of the i-th
ant. There is no position on the tree (neither leave nor ramification) with more than one ant. In the line
n+k+2 there is one integer
l, 1<=l<=500, l says how many times a ladybug lands on the tree. In each of the following
l lines one positive integer (not grater than n) is written.
These numbers describe
the places in which the ladybug successively lands.
## OutputYour program should write ## Sample Input4 1 2 1 3 2 4 2 1 2 2 2 4 ## Sample Output1 0 4 2 ## FigureSubmitStatistics |