Description

As one can’t make a living from the prizes awarded at computer science competitions, you have decided to get into the art business—or, more precisely, into a certain museum you have chosen for your debut as an art thief. Unfortunately, this museum is guarded quite well: there are $𝐾$ watchmen patrolling the building, each touring on his own simple closed path through the museum.

To coordinate your operation, you use a map of the area which describes the museum as a set of $𝑀$ corridors connecting $𝑁$ corners, numbered from $1$ to $𝑁$. You start at corner $1$, whereas your target —a valuable exhibit—is located at corner $𝑁$. Of course, one can reach any corner of the museum from any other corner, but you are not sure whether this is possible without getting noticed, that is, without ever being at the same corner as a watchman and without passing a watchman in a corridor.

Fortunately, you got your hands on the guard roster. So you know for each watchman where he is located at the beginning and which route he is taking. Each minute, a watchman moves from his current position to the next corner on his route, and you can either stay at your current position or move to an adjacent corner. You observed that no two of the watchmen’s routes intersect and that neither your starting position nor your target is contained in any of them.

Write a program that uses this information to either calculate the minimum amount of time in minutes you need to safely reach your target without being noticed or to decide that this is impossible.

Input

The first line of input contains the integers $𝑁$ and $𝑀$ described above. The following $𝑀$ lines each contain two integers $𝑢$ and $𝑣$ ($1 \le 𝑢, 𝑣 \le 𝑁, 𝑢 \not = 𝑣$), meaning that there is a corridor directly connecting corners $𝑢$ and $𝑣$. It is guaranteed that at most one corridor directly connects any two given corners.

The next line contains the single integer $𝐾$ described above. Then $𝐾$ lines follow;the $i$ th of these lines contains a sequence of integers, describing the route of the $i$ th watchman as follows: The first integer $ℓ_i$ gives the number of distinct corners on the route. Then $ℓ_i$ pairwise distinct integers $v_1,\ldots,v_{ℓ_i}$ specify the sequence of corners the watchman passes on his route. More precisely, the watchman starts at corner $v_1$, in one minute he will be at $v_2$, and so on; after $ℓ_i$ minutes he will be at $v_1$ again.

Output

Your program should output a single line. This should consist of an integer, the minimum amount of time in minutes you need to safely reach your target, or the string impossible if there is no way to achieve this.

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

Limits And Hints

We always have $1 \le N \le 2.5 \times 10^5$, $1 \le M \le 3 \times 10^6$, $3 \le ℓ_i \le 1.5\times 10^3$, $\sum ℓ_i \le 2750$.

• Subtask 1（5 points）：$N,M \le 10^5$, $K=1$, $ℓ_1 \le 125$.
• Subtask 2（10 points）：$N,M \le 10^5$, $\sum ℓ_i \le 125$ and no corridor connects the routes of two distinct watchmen.
• Subtask 3（10 points）：$ℓ_i \le 200$, $\sum ℓ_i \le 350$ and no corridor connects the routes of two distinct watchmen.
• Subtask 4（10 points）：No corridor connects the routes of two distinct watchmen.
• Subtask 5（25 points）：$\sum ℓ_i \le 125$.
• Subtask 6（20 points）：$ℓ_i \le 200$，$\sum ℓ_i \le 350$.
• Subtask 7（20 points）：No further constraints.