Bitaro's Party

Time limit2sMemory limit512 MB

Summary

For each party at town T, find the largest number of canals any non-busy friend who can reach T must travel, given the busy friends listed for that party.

Level: Medium7 of 10
Topics: Dynamic programming, Graph
Solved: No attempts yet

Statement

There are $N$ towns of beavers numbered from $1$ to $N$ in descending order of their heights. No two towns have the same height. There are $M$ canals connecting two different towns, each flowing in one direction. The $i$ -th canal ( $1 \le i \le M$ ) flows from town $S_i$ to town $E_i$ . Every canal flows from a higher town to a lower town, so you cannot move against the flow of the canals.

Bitaro, a beaver, has $N$ friends, and one of them lives in each town.

Bitaro holds $Q$ parties, inviting his friends. At the $j$ -th party ( $1 \le j \le Q$ ), $Y_j$ friends are too busy to attend. The $j$ -th party is held in town $T_j$ . A friend who cannot travel from their town to town $T_j$ using only canals cannot attend either. All other friends come to the party.

Each friend travels to the party's town using canals. There may be several paths they can take. Bitaro's friends love canals, so each friend takes the path with the largest number of canals.

Bitaro wants to know how many canals the attendee who uses the most canals travels.

Given the town of each party and the list of busy friends for each of the $Q$ parties, write a program that calculates how many canals the attendee who uses the most canals travels.

Input

The first line contains three space-separated integers $N$ , $M$ , and $Q$ , the number of towns, canals, and parties.

Each of the next $M$ lines contains two integers $S_i$ and $E_i$ , meaning a canal flows from town $S_i$ to town $E_i$ .

Each of the next $Q$ lines contains $T_j$ and $Y_j$ , followed by $Y_j$ integers $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$ . These mean the $j$ -th party is held in town $T_j$ , and the friends living in towns $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$ are busy.

Output

Print $Q$ lines. The $j$ -th line contains the number of canals used by the attendee who uses the most canals for the $j$ -th party. If nobody can attend the $j$ -th party, print $-1$ .

Constraints

$1 \le N \le 100000$ .
$0 \le M \le 200000$ .
$1 \le Q \le 100000$ .
$1 \le S_i < E_i \le N$ for $1 \le i \le M$ .
$(S_i, E_i) \ne (S_j, E_j)$ for $1 \le i < j \le M$ .
$1 \le T_j \le N$ for $1 \le j \le Q$ .
$0 \le Y_j \le N$ for $1 \le j \le Q$ .
$1 \le C_{j,1} < C_{j,2} < \cdots < C_{j,Y_j} \le N$ for $1 \le j \le Q$ .
$Y_1 + Y_2 + \cdots + Y_Q \le 100000$ .

Examples2

Example 1

Input

Expected output

1
3
0

Example 2

Input

12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8

Expected output