Each morning Byteasar the Postman has to visit every street of his district and deliver the mail.
All of the roads are one-way and are connected by the (pairwise distinct) crossroads.
A pair of crossroads may be connected by two roads at the most: one for each
of the opposing directions.
The crossroads are numbered from 1 to .
Byteasar starts and ends each route in Byteotian Post headquarters, by the first crossroads. For as long as it can be remembered Byteasar had been choosing his route by himself, but recently the board of directors has issued a new regulation, limiting the freedom of choice of the routes. Each postman has been assigned a collection of route fragments - a set of sequences of crossroads. Byteasar has to choose such a route which:
Write a programme which:
The first line of the standard input contains two integers and
separated by a single space,
,
,
denoting the number of crossroads and roads, respectively.
The following
lines contain the descriptions of the roads:
two integers
,
, separated
by a single space,
,
, denote a one-way road from
the crossroads
to
.
Each (ordered) pair
appears in the data once at the most.
In the following line there is an integer
,
,
denoting the number of assigned sequences.
The successive
lines contain the descriptions of these sequences.
A description consists of an integer
,
,
and a sequence
of crossroads' numbers.
The numbers in a line are separated by single spaces.
The total length of all of the sequences does not exceed
.
Your programme should write in the first line of the standard output:
6 10 1 5 1 3 4 1 6 4 3 6 3 4 4 3 5 6 6 2 2 1 4 3 1 5 6 3 3 4 3 4 4 3 6 4 3 5 6 2the correct outcome is:
TAK 1 3 4 3 6 4 1 5 6 2 1