Patrol

Time limit: 1s
Memory limit: 256MB
Input:
Output:

Task

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 KK patrols, indexed from 00 to K1K-1 to guard the manholes connected to the sewer system.
There are NN manholes, indexed from 00 to N1N-1 and MM tunnels connecting pairs of them. Valerio's friend Filippo is waiting for him nearby manhole N1N-1, if he can reach it, he will escape safely.

Valerio starts from manhole 00 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 LiL_i manholes, indexed from 00 to Li1L_i-1. Patrol ii is initially guarding manhole Hi,0H_{i,0}, every minute it moves from manhole Hi,jH_{i,j} to manhole Hi,j+1H_{i,j+1}, after reaching manhole Hi,Li1H_{i,L_i-1}, it return to manhole Hi,0H_{i,0}.

Input

The first line contains three integers NN, MM and KK, the numbers of manholes, tunnels and patrols respectively. (1N1041 \leq N \leq 10^4), (1M51041 \leq M \leq 5*10^4), (0K1050 \leq K \leq 10^5).

The following MM lines contain two integers each: the manholes connected by tunnel ii.

The following KK lines contain the integer LiL_i followed by LiL_i integers H0,H1,,HLi1H_0, H_1, \ldots, H_{L_{i-1}}. (1Li71 \leq L_i \leq 7).

Restrictions

  • For tests worth 2020 points, (N100N \leq 100, M100M \leq 100, K500K \leq 500).
  • For tests worth 1010 more points, (K=0K = 0).
  • For tests worth 3030 more points (Li2L_i \leq 2) for i=0...K1i = 0...K - 1.

Output

You need to write a single line with an integer: the minimum amount of minutes needed to get from manhole 00 to manhole N1N-1, or 1-1 if it is impossible to do.

Example 1

stdin

3 2 1
0 1
1 2
3 1 2 0

stdout

2

Example 2

stdin

5 4 3
0 1
1 2
2 3
3 4
3 4 2 3
2 2 1
2 4 3

stdout

5

Explanation

In the first sample case Valerio is beneath manhole 00, and there is a single patrol watching manhole 11.
In the first minute Valerio moves to manhole 11 while the patrol moves to manhole 22.
In the second minute Valerio moves to manhole 22 while the patrol moves to manhole 00, making it out safely in 22 minutes.

In the second sample case it takes Valerio 55 minutes to escape while avoiding the patrols.

Problem info

ID: 302

Editor: Dap

Author:

Source: IIOT 2022-23 Round I

Tags:

IIOT 2022-23 Round I

Log in or sign up to be able to send submissions!