In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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 ant-guards (numbered from to ). 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:
Write a program which:
In the first line of the standard input there is one integer , equal to the number of leaves and ramifications on the tree, . We assume that leaves and ramifications are numbered from to . Each of the following lines describes a branch --- a description consist of two integers and , it means that a given branch connects places and of the tree. The branches allow to get from one place to the another. In the -st line there is one integer , and ; is equal to number of ants that guard the tree. In each of the following lines one positive integer (not greater than ) is written. An integer written in -th line is a start position of the -th ant. There is no position on the tree (neither leaf nor ramification) with more than one ant. In the line there is one integer , , says how many times a ladybug lands on the tree. In each of the following lines one positive integer (not greater than ) is written. These numbers describe the places in which the ladybug successively lands.
Your program should write lines to the standard output. In the -th line there should be written two integers separated by a single space - the final position of the -th ant (number of a ramification or a leaf) and the number indicating how many times the -th ant chased the ladybug away.
For the input data:
4 1 2 1 3 2 4 2 1 2 2 2 4
the correct result is:
1 0 4 2
Task author: Krzysztof Lorys.