Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Prepared by Ibrahim Mesecan.
My grand-grand-grandfather
In a table you are given the parent (or ancestor)
relationship of some people.
For example
3 5
4 7
where 3 is the child (or grandchild) of 5,
and 4 is the child of 7, etc. Note:
if one has been given two ancestors, the
smaller one is the ancestor of this person. And, the ancestor
of the second person do not change. And in the beginning, everone
is parent of himself.
Question:Write a program that
finds the top most ancestors of k
people.
Input specification
You are first given three numbers: the number of
people (n: where people have the IDs from 1 to n);
the number of parent child relationships (m) and
the number of people whose top most ancestors are
asked (k) where 1 ≤ (n, m, k) ≤ 10,000.
Output specification:
For all k people, find their top most ancestors and
show. If anyone is not provided parent information,
show his own id.
Sample Input
7 5 4
3 5
4 7
5 4
6 4
1 2
3
6
2 1
|
Sample Output
3
4
2
1
|
Для отправки решений необходимо выполнить вход.
|