스키 리조트

당신은 미국에서 이름난 스키 리조트의 주인이다. 리조트 곳곳의 스낵 가판대에 알맞은 간식을 채워 넣어 매출을 올리려 한다.

스키 리조트는 산 위에 있다. 손님은 스키 리프트를 타고 산꼭대기에 올라간 뒤, 그곳에서 스키를 타고 산의 여러 지점으로 내려간다.

산에는 $n$개의 구역이 있고, 각 구역에는 $1$부터 $n$까지 번호가 붙어 있다. 산꼭대기는 $1$번 구역이다. 구역들은 스키 코스로 연결되어 있으며, 모든 스키 코스는 엄격하게 내리막이다. 즉 한 구역을 떠나면 스키 리프트를 타지 않고는 그 구역으로 다시 돌아올 수 없다. 모든 구역($1$번 구역 포함)에는 스낵 가판대가 정확히 하나씩 있다.

리조트 주인으로서 당신은 손님을 더 잘 대접하기 위해(그리고 돈을 더 벌기 위해) 가판대에 간식을 얼마나 효과적으로 배치할 수 있는지 알고 싶다. 그래서 설문 조사를 하고, 그 결과를 서로 독립적인 여러 질의로 분석하려 한다. 설문에 참여한 손님마다 가장 좋아하는 간식이 하나 있고, 즐겨 찾는 구역의 목록이 있다. 당신은 각 손님이 좋아하는 간식을 가판대에 어떻게 채우는 것이 가장 좋은지 알고 싶다.

각 질의는 한 손님이 즐겨 찾는 구역들의 집합과 수 $k$로 이루어진다. 이 손님이 좋아하는 간식을 산 위의 가판대 정확히 $k$곳에 채우는 방법 가운데 다음 조건을 모두 만족하는 방법의 수를 구하라.

1. 손님이 즐겨 찾는 각 구역에 대해, $1$번 구역에서 그 구역까지 가는 모든 스키 코스 경로를 통틀어 이 간식을 파는 가판대가 정확히 하나 있어야 한다. 다시 말해 손님이 이 간식을 살 가판대를 둘 이상 중에서 고를 수 있어서는 안 된다. 따라서 $1$번 구역에서 그 구역까지 가는 어떤 경로 위에 놓인 구역(두 끝 구역 포함) 가운데 간식을 채운 가판대는 정확히 하나이고, $1$번 구역에서 그 구역까지 가는 모든 경로가 그 가판대가 있는 구역을 지난다.
2. 이 간식을 채운 $k$곳의 가판대는 각각 $1$번 구역에서 질의 집합의 어떤 구역까지 가는 스키 코스 경로 위에 놓여 있어야 한다.

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.

첫째 줄에 세 정수 $n$, $m$, $q$가 공백으로 구분되어 주어진다. $n$($1 \le n \le 10^5$)은 산에 있는 구역의 수, $m$($1 \le m \le n + 50$)은 스키 코스의 수, $q$($1 \le q \le 10^5$)는 질의의 수이다.

다음 $m$개의 줄에는 각각 두 정수 $x$와 $y$($1 \le x, y \le n$, $x \ne y$)가 주어진다. 이는 $x$번 구역에서 $y$번 구역으로 내려가는 스키 코스를 뜻한다. 두 구역 사이에는 스키 코스가 많아야 하나 있다. 모든 구역은 $1$번 구역에서 스키 코스를 몇 개 이어 타서 도달할 수 있다.

다음 $q$개의 줄에는 각각 공백으로 구분된 정수들이 주어진다. 각 줄은 $k$와 $a$로 시작하고, 그 뒤에 정수 $i$가 $a$개 이어진다. $k$($1 \le k \le 4$)는 이 손님이 좋아하는 간식을 채울 가판대의 수, $a$($1 \le a \le n$)는 질의 집합에 속한 구역의 수이고, $a$개의 정수 $i$($1 \le i \le n$)는 질의 집합에 속한 구역의 번호이다. 한 질의 안에서 같은 $i$가 두 번 나오지 않는다.

모든 질의의 $a$의 합은 $100\,000$을 넘지 않는다.

정수 $q$개를 한 줄에 하나씩, 빈 줄 없이 출력한다. 각 정수는 해당 질의에서 간식을 채울 가판대를 고르는 방법의 수이며, 질의가 입력에 주어진 순서대로 출력한다. 어떤 구역이 한 방법에서는 선택되고 다른 방법에서는 선택되지 않으면 두 방법은 서로 다르다.