Bitaro의 파티

시간 제한2초메모리 제한512 MB

요약

각 파티에서 T 마을에 도달할 수 있으면서 바쁘지 않은 친구가 지나는 간선 수의 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그래프
정답자: 아직 제출이 없습니다

문제

높이가 서로 다른 $N$ 개의 마을에 높은 순서대로 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다. 같은 높이의 마을은 없다. 서로 다른 두 마을을 잇는 $M$ 개의 운하가 있고, 각 운하는 한쪽 방향으로만 흐른다. $i$ 번째 운하( $1 \le i \le M$ )는 $S_i$ 번 마을에서 $E_i$ 번 마을로 흐른다. 모든 운하는 높은 마을에서 낮은 마을로 흐르므로, 운하의 흐름을 거슬러 이동할 수 없다.

비버 Bitaro에게는 친구가 $N$ 명 있고, 각 마을에 한 명씩 살고 있다.

Bitaro는 친구들을 초대해 파티를 $Q$ 번 연다. $j$ 번째 파티( $1 \le j \le Q$ )에는 $Y_j$ 명의 친구가 바빠서 참석하지 못한다. $j$ 번째 파티는 $T_j$ 번 마을에서 열린다. 운하만 따라 자기 마을에서 $T_j$ 번 마을까지 갈 수 없는 친구도 참석할 수 없다. 나머지 친구는 모두 파티에 온다.

각 친구는 운하를 따라 파티가 열리는 마을까지 온다. 갈 수 있는 경로가 여러 개일 수 있다. Bitaro의 친구들은 운하를 좋아해서, 운하를 가장 많이 지나는 경로를 골라야 한다.

Bitaro는 참석자 중 가장 많은 운하를 지나는 사람이 운하를 몇 개 지나는지 궁금하다.

파티가 열리는 마을과 $Q$ 번의 파티마다 바쁜 친구 목록이 주어질 때, 가장 많은 운하를 지나는 참석자가 지나는 운하의 수를 구하는 프로그램을 작성하라.

입력

첫 줄에 마을의 수 $N$ , 운하의 수 $M$ , 파티의 수 $Q$ 가 공백으로 구분된 정수로 주어진다.

다음 $M$ 개의 줄에는 정수 $S_i$ 와 $E_i$ 가 주어지며, 마을 $S_i$ 에서 마을 $E_i$ 로 운하가 흐른다는 뜻이다.

다음 $Q$ 개의 줄에는 $T_j$ 와 $Y_j$ 가 주어지고, 이어서 $Y_j$ 개의 정수 $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$ 가 주어진다. 이는 $j$ 번째 파티가 $T_j$ 번 마을에서 열리고, $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$ 번 마을에 사는 친구들이 바쁘다는 뜻이다.

출력

$Q$ 줄에 걸쳐 출력한다. $j$ 번째 줄에는 $j$ 번째 파티에서 가장 많은 운하를 지나는 참석자가 지나는 운하의 수를 출력한다. 참석할 수 있는 사람이 아무도 없으면 $-1$ 을 출력한다.

제한

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

예제2

예제 1

입력

예상 출력

1
3
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

예상 출력