== include(page="template/taskheader" task_id="patrol2") ==

Poveste şi cerinţă...

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 <tex> L_{i-1} </tex>. Patrol $i$ is initially guarding manhole <tex> H_{i,0} </tex>, every minute it moves from manhole <tex> H_{i,j} </tex> to manhole <tex>H_{i,j+1}</tex>, after reaching manhole <tex>H_{i,L_i-1}~</tex>, it return to manhole <tex>H_{i,0}</tex> .

h2. Date de intrare

Fişierul de intrare $patrol2.in$ ...

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 <tex> L_i </tex> followed by <tex>L_i </tex> integers <tex> H_0, H_1, \ldots, H_{L_{i-1} </tex>.
 

h2. Date de ieşire

În fişierul de ieşire $patrol2.out$ ...

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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* (1 ≤ $N$ ≤ 10^4^), (1 ≤ $M$ ≤ 5*10^4^), (1 ≤ $K$ ≤ 10^5^).
* (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$.
 

h2. Exemplu
table(example). |_. patrol2.in |_. patrol2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 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
|

h3. 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.

== include(page="template/taskfooter" task_id="patrol2") ==