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 n ant-guards (numbered from 1 to n). A ladybug threatens the culture, she always sits in places where aphides appear, (i.e. on leaves or ramifications). When a ladybug sits on the tree 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. 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.
Write a program which:
InputIn the first line of the text file MRO.OUT there is one integer n, 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.
Your program should write k lines in the output file MRO.OUT. In the i-th line there should be written two integers separated by a single space - the final position of the i-th ant (number of a ramification or a leaf) and the number indicating how many times the i-th ant chased the ladybug away.
4 1 2 1 3 2 4 2 1 2 2 2 4
1 0 4 2