PEG Judge - WC01 - The Thirteenth Floor

Woburn Challenge 2001

Problem 9: Operation Thirteenth Floor

How James Bond eluded CBS security in their own headquarters has long been a mystery – to avoid publicizing the secret phone number he used, the details were classified, but have now been cleared for public viewing. Below are excerpts from his report.

“With minimal effort, I was in CBS headquarters, having acquired my information. However, I was on the top floor and needed to escape from the building. I quickly made a collect call to London (just by dialing 10-10-321, then 1, then the number, for only 10¢ a minute) where I asked P to fix the elevators for me. You see, I knew that before CBS security could mobilize, they needed to hold a board meeting and some focus groups to decide on an appropriate course of action. To hold a meeting, all the people would need to be on the same floor at the same time. Thus, if I could slow down their ability to meet in one place, I would have enough time to escape. Showing an unusual burst of competence, P quickly hacked into the elevator control system (which just happens to be accessible by Internet), and changed the elevator controls so that each elevator now followed a fixed route regardless of what buttons are pushed (i.e. it might visit floors 2-4-8-3-2-4-8-3…).

Having already patched into CBS communication channels, I knew that security had been notified that a meeting was urgently necessary. The chief of security had determined that the elevators were “wonky” and was trying to determine what floor to meet on so that the meeting could be held at the earliest possible time. I knew where everyone in the building was located and P had told me the “schedules” that the elevators follow, so I was able to figure out the shortest amount of time before a meeting could have been held, and on which floor this meeting could take place. It’s a good thing the building had no stairs. Now I knew how much time I had to escape and which floor to avoid.”

Input

The first line of contains T, the number of test cases.
The first line of each test case contains the positive integers F, the number of floors in the building, E, the number of elevators, and P, the number of people (1 ≤ F,E,P ≤ 50). The next line contains P integers giving the locations of all the people in the building. Each of the next E lines contains the “schedule” for an elevator: a positive integer N (2 ≤ N ≤ 50) representing the number of floors which that elevator visits, followed by N integers between 1 and F giving that elevator’s schedule. No two consecutive integers in the schedule will be identical (including the first and last).

Assume the following:

All elevators move at the speed of 1 floor/minute
Every elevator starts with its doors open on the first floor listed in its schedule at 12:00
A person can get in/out of an elevator instantaneously

Output

For each test case, output a line containing M, the least number of minutes before a meeting can be held, and F the floor on which the meeting could take place at this time. If it could take place on several floors, choose the lowest (nosebleeds can be deadly). If no meeting is possible, output Impossible.