문제>제한에서 (S,E)쌍이 ,로 연결되는게 아니라 not equal로 연결되어야 합니다.

[JOISC 17/18 3-2] BITARO'S PARTY

문제

1부터 N까지 높이에 대한 내림차순으로 번호가 매겨진 N개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) M개의 운하는 서로 다른 마을을 단방향으로 연결합니다. i번째 운하(1\le i\le M)은 높은 S_i에서 낮은 E_i로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다.

비버 Bitaro의 N명의 친구들은 N개의 마을에 살고 있습니다.

Bitaro는 Q번의 파티를 열며, 친구들을 초대할 것입니다. j번째 파티에는 Y_j명의 친구들이 바빠서 못 온다는 것이 알려져 있습니다. j번째 파티는 T_j 마을에서 열리므로 T_j 마을에 갈 수 없는 친구들도 참석하지 못합니다. 이 두 경우가 아닌 친구들만 파티에 참석할 수 있습니다.

각각의 친구들은 운하들을 통해 파티가 열리는 마을에 옵니다. 그 경로는 여러가지가 될 수 있습니다. 하지만 Bitaro의 친구들은 운하를 좋아하므로 가장 많은 운하가 있는 길 중에서 하나를 택합니다.

Bitaro는 가장 많은 수의 운하를 사용한 친구가 얼마나 많은 운하를 사용하는지 궁금해합니다. 파티에 열리는 N개의 마을들과 Q번의 파티에 대한 바쁜 친구들의 목록을 고려해 가장 많은 수의 운하를 사용하는 친구가 얼마나 많은 운하를 사용하는지 계산하는 프로그램을 작성해 주십시오.

입력

표준 입출력으로 다음 데이터들이 주어집니다.

• 첫번째 줄은 N, M, Q가 공백으로 나뉘어 주어집니다. 각각 마을의 개수 N과 운하의 개수 M, 파티의 횟수 Q를 의미합니다.
• i번째 줄(1\le i\le M)은 M개의 줄에 걸쳐 S_i와 M_i들이 주어집니다. S_i에서 E_i으로 가는 단방향 운하입니다.
• j번째 줄(1\le j\le Q)은 Q개의 줄에 걸쳐 각 줄에 T_j, Y_j, C_{j,1}, C_{j,2}, \cdots, C_{j,Y_j}가 주어집니다. T_j에서 열리는 j번째 파티에 C_{j,1},C_{j,2},\cdots ,C_{j,Y_j}들이 바빠서 불참한다는 의미입니다.

출력

Q개의 줄에 걸쳐 출력합니다. j번째(1\le j\le Q) 줄에는 가장 많은 운하를 사용한 친구가 사용한 운하의 개수를 출력합니다. 만약 아무도 참석하지 못한다면 그 줄에는 -1을 출력합니다.

제한

• 1\le N\le 10^5
• 0\le M\le 2\times 10^5
• 1\le Q\le 10^5
• 1\le S_i<E_i\le N\ (1\le i\le M)
• (S_i,E_i)\neq(S_j,E_j)\ (1\le i<j\le M)
• 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\ (1\le j\le Q)
• Y_1+Y_2+\cdots +Y_Q\le 10^5

서브태스크