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

1771. A Deputy's Morning

Time limit: 1.0 second
Memory limit: 64 MB
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.


4 3
1 4 -1
4 1 -1
3 1 4 2 -1
07:00 1
07:10 3
13 55
Problem Author: Alex Samsonov
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010