Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | patrol2.in, patrol2.out | Sursă | IIOT 2022-23 Runda I |
| Autor | Edoardo Morassutto | Adăugată de |  Buca Mihnea-Vicentiu •UnknownPercentage |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Patrol2
Valerio is robbing a bank, but an alarm started ringing as he was trying to break into the caveau.
He needs to get out as fast as possible through the twisted sewer tunnels running nearby the bank.
The police is already looking for him and has sent K patrols, indexed from 0 to K-1 to guard the manholes connected to the sewer system.
There are N manholes, indexed from 0 to N-1 and M tunnels connecting pairs of them. Valerio's friend Filippo is waiting for him nearby manhole N-1, if he can reach it, he will escape safely.
Valerio starts from manhole 0 and, every minute, he can choose to move to a manhole adjacent to the one he is in or to stay another minute under the same manhole.
Each police patrol guard L i manholes, indexed from 0 to L i-1. Patrol i is initially guarding manhole H i,0, every minute it moves from manhole H i,j to manhole 
, after reaching manhole 
, it return to manhole 
.
Date de intrare
The first line contains three integers N, M and K, the numbers of manholes, tunnels and patrols respectively.
The following M lines contain two integers each: the manholes connected by tunnel i.
The following K lines contain the integer L_i followed by L i integers H 0, H 1, ..., H Li-1.
Date de ieşire
You need to write a single line with an integer: the minimum amount of minutes needed to get from manhole 0 to manhole N-1, or -1 if it is impossible to do.
Restricţii
- (1 ≤ N ≤ 104), (1 ≤ M ≤ 5*104), (1 ≤ K ≤ 105).
- (1 ≤ L i ≤ 7).
- For the first subtask, (N ≤ 100, M ≤ 100, K ≤ 500).
- For the second subtask, (K = 0).
- For the third subtask, (L i ≤ 2) for i = 0...K - 1.
Exemplu
| patrol2.in | patrol2.out |
|---|---|
| 3 2 1 0 1 1 2 3 1 2 0 | 2 |
| 5 4 3 0 1 1 2 2 3 3 4 3 4 2 3 2 2 1 2 4 3 | 5 |
Explicaţie
In the first sample case Valerio is beneath manhole 0, and there is a single patrol watching manhole 1.
In the first minute Valerio moves to manhole 1 while the patrol moves to manhole 2.
In the second minute Valerio moves to manhole 2 while the patrol moves to manhole 0, making it out safely in 2 minutes.
In the second sample case it takes Valerio 5 minutes to escape while avoiding the patrols.
