ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2004 Round 1

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Chase in Subway

Time limit: 0.5 second
Memory limit: 64 MB
The police has let a criminal slip. He has disappeared in the complicated grid of subway lines, where a chase is senseless. But the criminal does not know that there is a radio beacon attached to his clothes. The beacon sends a signal to the police from each of the stations visited or passed through by the criminal (it is not possible to detect a signal from a tunnel between stations, because the signal is too faint). Having the information about the sequence of stations passed by the criminal, the police wants to determine the stations where the criminal might be going to, in order to set watch posts at these stations.
The police knows that the criminal behaves quite logically; he has a goal (the subway station where his shelter is located), and he is moving there using one of the shortest routes. For the criminal, the length of a route is determined by the number of spans only (in the subway, a span is a tunnel between two adjacent stations). The length of a route does not depend on the lengths of spans or the number of line changes.


The first line of input contains the number N of lines in the subway (1 ≤ N ≤ 50). Each of the next N lines contains a description of the corresponding line. A description starts with an integer K (2 ≤ K ≤ 50), which is the number of stations of the line. Then there are the numerical indices of the stations of the line, in the order in which the stations are on the line. The indices are integers from 1 to 32767. All the numbers are separated with spaces. If there is the same station index in the descriptions of two different lines, then these lines have an intersection at this station, where a change can be made. The last line of input contains surveillance data: an integer M ≥ 1, which is the number of stations where the criminal was registered, and M numbers, which are the indices of these stations in the order in which the criminal visited them.


You should output the indices of all stations that can be the goal of the criminal, in the ascending order, one per line.


2 61 62
5 75 20 85 50 61
3 10 20 30
3 30 20 85
Problem Author: Idea - Leonid Volkov, prepared by Alexander Somov, Leonid Volkov, Igor Goldberg
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004
To submit the solution for this problem go to the Problem set: 1314. Chase in Subway