Problem Description

Given an undirected graph with \( N \) nodes and \( M \) edges, there are \( K \) guards. Each guard \( i \) will traverse \( \ell_i \) nodes, which are \( v_1, v_2, \cdots, v_{\ell_i} \). The mechanism is that the guard starts at node \( v_1 \), and at minute \( 0 \), it is at node \( v_1 \); at minute \( 1 \), it moves from node \( v_1 \) to node \( v_2 \); at minute \( 2 \), it moves from node \( v_2 \) to node \( v_3 \); and so on, until at minute \( \ell_i-1 \), it moves from node \( v_{\ell_i-1} \) to node \( v_{\ell_i} \); at minute \( \ell_i \), it moves from node \( v_{\ell_i} \) to node \( v_1 \), and this cycle continues indefinitely.

You are a thief, aiming to travel from node \( 1 \) to node \( N \). At minute \( 0 \), you are at node \( 1 \). You can move directly from one node to another, but you must ensure that the path between these nodes does not have any guards on it, nor do the guards traverse the edges that form this path. Each edge takes one minute to traverse. It is guaranteed that no two guards' paths intersect, and neither the start nor the end node is on any guard's path.

You need to determine the minimum number of minutes required to reach node \( N \) without being detected by the guards, or determine that it is impossible.

Input Format

The first line contains two integers \( N \) and \( M \), representing the number of nodes and edges, respectively.

The next \( M \) lines each contain two integers \( u \) and \( v \), representing an edge between nodes \( u \) and \( v \).

The \( M+2 \)-th line contains an integer \( K \), representing the number of guards.

The next \( K \) lines each start with an integer \( \ell_i \), representing the path length of guard \( i \), followed by \( \ell_i \) integers \( v_1, v_2, \cdots, v_{\ell_i \), describing the path.

Output Format

Output a single integer representing the minimum number of minutes required, or output impossible if it is not possible.

Sample Input and Output

Sample Input #1

6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 3 2 5 4

Sample Output #1

4

Sample Input #2

6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 4 5 2 3

Sample Output #2

5

Sample Input #3

11 13
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 5
6 8
8 9
9 10
10 8
9 11
3
3 4 2 3
3 7 6 5
3 10 8 9

Sample Output #3

impossible

Notes

Sample 1 Explanation

The path of the first guard is as follows:

A feasible way is:

• At minute \( 0 \), start at node \( 1 \);
• At minute \( 1 \), wait at node \( 1 \);
• At minute \( 2 \), move to node \( 2 \);
• At minute \( 3 \), move to node \( 5 \);
• At minute \( 4 \), move to node \( 6 \).

Sample 2 Explanation

The graph and paths are the same as in Sample 1, but with different start and end points.

A feasible way is to move directly along the path \( 1 \to 2 \to 3 \to 4 \to 5 \to 6 \).

Data Constraints

This problem uses batched testing.

• Subtask 1 (5 pts): \( N, M \le 10^5 \), \( K = 1 \), \( \ell_1 \le 125 \).
• Subtask 2 (10 pts): \( N, M \le 10^5 \), \( \sum \ell_i \le 125 \), satisfying property A.
• Subtask 3 (10 pts): \( \ell_i \le 200 \), \( \sum \ell_i \le 350 \), satisfying property A.
• Subtask 4 (10 pts): Satisfying property A.
• Subtask 5 (25 pts): \( \sum \ell_i \le 125 \).
• Subtask 6 (20 pts): \( \ell_i \le 200 \), \( \sum \ell_i \le 350 \).
• Subtask 7 (20 pts): No special restrictions.
• Subtask Ex (0 pts): Extra Subtask.

For 100% of the data, \( 1 \le N \le 2.5 \times 10^5 \), \( 1 \le M \le 3 \times 10^6 \), \( 3 \le \ell_i \le 1500 \), \( \sum \ell_i \le 2750 \).

Property A states that no edge connects any two guards' paths.

Notes

Translated from BalticOI 2021 Day1 C From Hacks to Snitches.

见题面 Input 部分

见题面 Output 部分