eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Secret Lab

Secret Lab

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

The famous agent 003 James Summer is planning to steal the new superbomb from the secret lab located in the mountains. The lab has several rooms that are connected by the doors. Each door can be opened by some researchers working in the lab with their electronic keys.

James can kill some researchers and take their keys. After that he can open all the doors that could be opened by the researchers. Also he can simply wait at the door until somebody passes by it and walk through it together with him. Agents have investigated the daily routine of the lab, so it is known about each researcher when he will walk through the doors.

When killing somebody, James increases the risk of failing his mission. Also the risk increases every second he stays on the territory of the lab. So James needs to choose which researchers’ keys he should get, and how to get to the room where the superbomb is located and out, minimizing the risk of mission failure.

Входные данные

The first line of the input file contains n — the number of rooms in the lab, m — the number of doors, and k — the number of researchers (2n20, 1m100, 1k10). Next m lines contain descriptions of doors — each door is described with numbers of rooms it connects. All doors are two way and can be opened from either side. Two rooms may be connected with more than one door.

After that k blocks describing researchers are provided. Each block starts with integer number r_i — the risk James takes if killing this researcher (1r_i32000). Then d_i is specified — the number of doors that this researcher can open, followed by the list of the doors. Doors are numbered starting from 1, as they are given in the file. The daily routine of the researcher follows. It starts with a_i — the number of doors that he opens daily, followed by a_i pairs of integer numbers — the number of the door that is opened by the researcher and the time when he does it, measured in seconds from the beginning of the workday (this time is positive and does not exceed the length of the workday, that is 8 hours or 28800 seconds). The events are listed in chronological order, a_i10. It is guaranteed that each researcher walks only through the doors that he can open with his electronic key.

James can start his mission any time during workday, and his mission must be over before the end of the workday. Every second he stays in a lab his risk increases by 1. James enters the lab in the hall, which is room number 1. The superbomb is located in the room number n. James must get to the room where superbomb is and return to lab hall. You should take into account that James needs at least one second before he can walk through two doors, in particular at least one second before he can walk through the first door. His mission is over one second after he enters the lab hall with the superbomb.

Выходные данные

If it is impossible to fulfil the mission, print "mission impossible" on the first line of the output file. In the other case print the minimal risk James must take to fulfil the mission.

After that print the plan James must follow. First print the number of researchers that must be killed followed by their numbers. After that print the time from the beginning of the workday James must enter the lab. It must be followed by the list of doors James passes, each with the time James passes it, measured in seconds from the beginning of the workday he enters the lab. The last number must be the time James’s mission is over.

Пример

Входные данные #1
3 3 2
1 2
2 3
2 3
3000
2  
2 3
3
2 3600
3 7200
2 14400
7000
2
1 2
3
1 600
1 3601
1 3700
Выходные данные #1
3101
1
1 
3600
1 3601
3 3602
3 3603
1 3700
3701
Источник Russian Teams Training Sessions in Petrozavodsk, Summer 2004, Andrew Stankevich Contest 8, Thursday, August 26, 2004