Eternal Siege

In the year \(8012\), on the night of May 12, an oracle descended: "Trust me, earn eternal life." Inspired by the divine word, the Chris legion embarks on a daring raid against Jasonland. Jasonland consists of \(N\) cities connected by \(M\) directed roads. City 1 (Oracle Town) is the starting point and city \(N\) is the enemy capital which houses the mighty temple of Zeng‒Blazer – the source of Jasonland's power. Destroying this temple will lead to the collapse of Jasonland.

However, some cities in Jasonland are protected by magical barriers. Each protected city has its barrier maintained by one or more barrier generators located in other cities. In order to enter a protected city, you must first destroy all the barrier generators that sustain its barrier.

You have an unlimited supply of self‐destructing robots. A robot, upon arriving at any city, may immediately self-detonate to destroy a single target – either a barrier generator (located in that city) or, if in the enemy capital, the great temple. (Note that the robot is destroyed along with its target.)

Traveling along any road takes one unit of time. Although the explosion is instantaneous, you may have to delay a robot’s departure so that all necessary barrier generators are destroyed before entering a protected city. That is, if a protected city \(v\) has barrier generators located in cities \(g_1, g_2, \dots, g_k\) then the robot entering \(v\) can only be dispatched after time \(\max\{d(1, g_1), d(1, g_2), \dots, d(1, g_k)\}\), where \(d(1, x)\) is the shortest travel time from city 1 to city \(x\) (ignoring barrier restrictions).

Your task is to determine the minimum time required to destroy Jasonland – that is, the minimum time \(T\) such that there exists a route from city 1 to city \(N\) whose travel time (number of roads taken) is at most \(T\) and for every protected city \(v\) on the route the clearance requirement \(\max_{g \in G(v)} d(1, g)\) is also at most \(T\). (You may send different robots on different routes concurrently; the overall time is determined by the slowest leg.)

Input and task summary:

• There are \(N\) cities and \(M\) directed roads.
• Then \(M\) lines follow, each containing two integers \(u\) and \(v\) indicating a road from city \(u\) to city \(v\).
• Next, an integer \(K\) denotes the number of protected cities. For each protected city, a line is given in the format: v k g1 g2 ... gk, meaning that city \(v\) is protected and its barrier is maintained by generators located in cities \(g_1, g_2, \dots, g_k\).
• A city that is not listed among these \(K\) lines has no barrier protection and can be entered freely.

Output: Output a single integer: the minimum time needed to destroy Jasonland’s temple in city \(N\). If it is impossible to reach city \(N\) under the conditions, output -1.

inputFormat

The input is given as follows:

N M
u1 v1
u2 v2
... (M lines total)
K
v1 k1 g1_1 g1_2 ... g1_k1
v2 k2 g2_1 g2_2 ... g2_k2
... (K lines total)

All numbers are integers. Cities are numbered from 1 to N. City 1 is the start and city N is the temple location.

outputFormat

Output a single integer: the minimum time required to complete the mission, or -1 if it is impossible.

sample

4 4
1 2
2 3
3 4
1 4
1
3 1 2

1