Description

You are given an undirected graph with $N$ vertices and $M$ edges. There are $K$ guards. Guard $i$ passes through $\ell_i$ vertices, which are $v_1, v_2, \cdots, v_{\ell_i}$. The movement rule is as follows: the guard starts at vertex $v_1$ at minute $0$. At minute $1$, it moves from $v_1$ to $v_2$; at minute $2$, it moves from $v_2$ to $v_3$; $\cdots$; at minute $\ell_i - 1$, it moves from $v_{\ell_i - 1}$ to $v_{\ell_i}$; at minute $\ell_i$, it moves from $v_{\ell_i}$ back to $v_1$. Then it repeats this cycle forever.

You are a thief. You want to go from vertex $1$ to vertex $N$. That is, at minute $0$ you are at vertex $1$. You may move directly from one vertex to another, but you must traverse a path between these two vertices. You must ensure that there is no guard on any vertex along this path, and also that no guard traverses any edge that belongs to this path. Traversing each edge takes you exactly one minute. It is guaranteed that the routes of any two guards are vertex-disjoint, and that both the start and the end vertices are not on any guard route.

You need to find the minimum number of minutes to reach vertex $N$ without being detected by the guards, or report that it is impossible.

Input Format

The first line contains two integers $N, M$, the number of vertices and edges.

The next $M$ lines each contain two integers $u, v$, describing an edge.

Line $M + 2$ contains an integer $K$, the number of guards.

The next $K$ lines each start with an integer $\ell_i$, the length of the guard's route, followed by $\ell_i$ integers $v_1, v_2, \cdots, v_{\ell_i}$ describing the route.

Output Format

Output one line containing one integer, the minimum number of minutes required, or output impossible if there is no solution.

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

4

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

5

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

impossible

Hint

Sample 1 Explanation

The route of guard $1$ is as follows:

One feasible way is:

• At minute $0$, start at vertex $1$.
• At minute $1$, wait at vertex $1$.
• At minute $2$, move to vertex $2$.
• At minute $3$, move to vertex $5$.
• At minute $4$, move to vertex $6$.

Sample 2 Explanation

The graph and routes are the same as in sample 1, but the start and end vertices are different.

One feasible way is: do not wait, and go directly along $1 \to 2 \to 3 \to 4 \to 5 \to 6$.

Constraints

This problem uses bundled testdata.

• 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$, and satisfies Property A.
• Subtask 3 (10 pts): $\ell_i \le 200$, $\sum \ell_i \le 350$, and satisfies Property A.
• Subtask 4 (10 pts): satisfies 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 testdata, $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 means that there is no edge connecting any two guard routes.

Notes

Translated from BalticOI 2021 Day1 C From Hacks to Snitches。

Translated by ChatGPT 5