시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB317673314.537%

문제

There are N towns of beavers numbered from 1 to N in the descending order of their heights. No two towns have the same height. There are M canals connecting two different towns unidirectionally. The i-th canal (1 ≤ i ≤ M) flows from town Si to town Ei. These canals flow from high towns to low towns. You cannot move against flow of the canals.

Bitaro, a beaver, has N friends, one of whom lives in each of N towns.

Bitaro is going to have parties Q times, inviting his friends. It is known for the j-th (1 ≤ j ≤ Q) party that Yj friends are too busy to attend it. The j-th party is held in town Tj, so his friends who cannot go from their towns to town Tj only via canals cannot attend it either. Other friends come to the party.

Each friend come to the town where the party is held via canals. There may be several paths they can take. But Bitaro’s friends love canals, so they must choice one of the paths which have the largest number of canals.

Bitaro wonders how many canals the attendant who uses the largest number of canals uses.

Given the indexes of the towns where the parties are held and lists of busy friends for the Q parties, write a program which calculates how many canals the attendant who uses the largest number of canals uses.

입력

Read the following data from the standard input.

  • The first line of input contains three space separeted integers N, M, Q. These mean there are N towns of beavers and M canals and Q parties Bitaro has.
  • The i-th line (1 ≤ i ≤ M) of following M lines contains two space separated integers Si and Ei. These mean the canal flows from Si to Ei unidirectionally.
  • The j-th line (1 ≤ j ≤ Q) of following Q lines contains two space separated integers Tj , Yj and Yj space separeted integers Cj,1, Cj,2, ..., Cj,Yj. These mean the j-th party is held in town T j and friends living in town Cj,1, Cj,2, ...,Cj,Yj are busy.

출력

Output contains Q lines. The j-th line (1 ≤ j ≤ Q) contains the number of canals the attendant who uses the largest number of canals uses for the j-th party. If no one can attend the j-th party, the j-th line contains -1.

제한

  • 1 ≤ N ≤ 100 000.
  • 0 ≤ M ≤ 200 000.
  • 1 ≤ Q ≤ 100 000.
  • 1 ≤ Si < Ei ≤ N (1 ≤ i ≤ M).
  • (Si , Ei) , (Sj , Ej) (1 ≤ i < j ≤ M).
  • 1 ≤ Tj ≤ N (1 ≤ j ≤ Q).
  • 0 ≤ Yj ≤ N (1 ≤ j ≤ Q).
  • 1 ≤ Cj,1 < Cj,2 < · · · < Cj,Yj ≤ N (1 ≤ j ≤ Q).
  • Y1 + Y2 + · · · + YQ ≤ 100 000.

서브태스크

번호배점제한
17

N ≤ 1 000, M ≤ 2 000, Q = 1.

27

Q = 1

386

There are no additional constraints.

예제 입력 1

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

예제 출력 1

1
3
0

Among the friends attending the first party (the friends living in town 2, 3 or 4), the friends living in town 2 or 3 go to town 4, where the party is held, via the largest number of canals. This number is 1, so output 1.

Among the friends attending the second party (the friends living in town 1, 4, or 5), the friend living in town 1 goes to town 5, where the party is held, via the largest number of canals. This number is 3, so output 3.

The friend living in town 2 is the only one who attends the third party. He uses no canals, so output 0.

예제 입력 2

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

예제 출력 2

1
-1
3
1
3
-1
5
2
4
4

채점 및 기타 정보

  • 예제는 채점하지 않는다.