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

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 $H_{i,j+1}$ , after reaching manhole $H_{i,L_i-1}~$ , it return to manhole $H_{i,0}$ .

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, \ldots, H_{L_{i-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 ≤ 10⁴), (1 ≤ M ≤ 5*10⁴), (1 ≤ K ≤ 10⁵).
(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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta