There are exactly n bus stops and m bus routes in Yekaterinburg. The
traffic system is designed so that the distance between two adjacent stops is
covered by any bus in exactly one minute. Each bus starts its journey no
earlier than 7 am at an integer number of minutes and lets the passengers in at
the first stop of its route. No two buses can go on the same route
simultaneously. When a bus reaches the last stop of its route, it does not turn
round and go back. There is no bus schedule in Yekaterinburg, and buses can go
arbitrarily allowing for the above constraints.
Deputy of the City Duma Leonid decided to set up a social control of the public
transportation system. At 06:50 he came out to the bus stop nearest to his home
with a notebook. He spoke to the people who were waiting there and they
explained him the way they usually used buses. Everybody who wants to get into
a bus comes to a bus stop in advance, no later than at 06:59. Boarding and
debussing take no time at all because people are in a hurry. Each passenger
chooses a bus by the following algorithm.
- If a bus that will take the passenger to the required bus stop arrives to
the stop, the passenger takes this bus.
- If several suitable buses come to the bus stop simultaneously, then the
passenger takes the bus that will take them to the required stop earlier.
- If there are several such buses, then the passenger takes the bus with
the minimal route number.
At exactly 7 am Leonid started writing the route numbers of the passing buses
and the times at which they arrived to the stop. The crowd at the stop was
gradually diminishing. Leonid was starting to enjoy the process when he
suddenly remembered that he had to attend a session of the Collegiate
Programming Committee. Then he got into the bus that came to the bus stop.
There were 42 people in the bus and 13 people entered the bus in addition to
Leonid. Help him determine the minimum and maximum number of those people that
would be in the bus when it arrived to the stop where Leonid had to get off.
The first line contains the integers n and m separated with a space (3 ≤ n, m ≤ 100). The i-th of the following m lines describes the route with number i. The description is a sequence of pairwise distinct numbers from 1 to n, which are the numbers of stops on the route. Each route contains at least two stops. The list ends with the number −1. The numbers in the list are separated with a space. Leonid lives near the stop with number 1 and plans
to get off at the stop with number 2.
The next line contains the number of buses k that Leonid recorded in
his notebook (1 ≤ k ≤ 100). Each of the following k lines contains the time when the bus arrived to the stop in the format hh:mm
(07 ≤ hh ≤ 23; 00 ≤ mm ≤ 59) and, after a space, the route number of this bus. The records in the notebook are time-ordered. The last in the list is the bus that Leonid took. It is known that the notebook also contains information on
all the buses that arrived to the stop simultaneously with the last bus. It is
guaranteed that the bus Leonid took has stop 2 in its route and that stop 1 is
not the first stop of this route.
Output two integers separated with a space. These should be the
minimum and maximum numbers of people going with Leonid the whole way from
stop 1 to stop 2.
1 4 -1
4 1 -1
3 1 4 2 -1
Problem Author: Alex Samsonov
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010