열대 식물원

식물학자 철수는 여러 반의 학생들과 함께 태국 최대의 식물원을 방문하기로 하였다. 이 넓은 식물원은 (0 부터 N-1 까지의 번호가 붙은) N 개의 연못과 M 개의 산책로로 구성되어 있다. 각 산책로는 서로 다른 두 연못을 연결하며, 양방향으로 모두 이동하는 것이 가능하다. 어느 연못이든지 최소 하나의 산책로가 연결되어 있다. 이 산책로들에는 철수가 좋아하는 아름다운 식물들이 많이 있다. 같은 반의 학생들은 함께 이동하며, 각 반이 산책을 시작하는 연못은 서로 다를 수 있다. 

철수는 아름다운 열대 식물들을 아주 좋아한다. 따라서, 철수와 각 반의 학생들은 어느 연못에서든 가장 아름다운 산책로를 선택하여 이용한다. 단, 그 산책로를 바로 직전에 이용한 경우에는 두 번째로 아름다운 산책로를 이용한다. 하지만, 현재 연못에 연결된 산책로가 단 하나뿐인 경우는 두 번째로 아름다운 산책로가 존재하지 않으므로 방금 사용한 산책로를 다시 이용하는 것을 허용한다. 철수는 식물학자이므로 두 산책로의 아름다운 정도가 같은 경우는 없다.

학생들은 식물에는 큰 관심이 없다. 학생들의 관심은 어떤 연못 P 옆에 위치한 고급 식당에서 점심 식사를 하는 것이다. 철수는 각 반의 학생들이 정확히 K 개의 산책로를 지난 다음 배가 고파질 것이라는 것을 알고 있다. 각 반 마다 K 의 값은 다를 수 있다. 이 상황 하에서 철수는 각 반에 대해 정확히 K 개의 산책로를 이용한 후 연못 P 에 도착하는 방법의 수가 얼마나 많은지 알고 싶다. 각 반에 대한 상황을 정리하면 다음과 같다.

• 각 반은 아무 연못에서나 출발핛 수 있다.
• 산책로를 선택하는 규칙은 위의 설명과 같다.
• 각 반은 정확히 K 개의 산책로를 이용한 다음에는 연못 P 에 도착해야 한다.

각 반이 P 로 가는 도중에 연못 P 를 지나는 것도 가능하다. 그러나, 마지막에는 반드시 P 에 도달하여야 한다.

당신은 연못과 산책로에 대한 정보를 받아서 Q 개의 반에 대한 해답을 찾아야 한다. 즉, Q 개의 K 값에 대한 해답을 생성해야 하는 것이다.

다음의 입력을 받는 count_routes(N, M, P, R, Q, G) 함수를 작성하라.

• N - 연못의 수. 연못은 0 부터 N-1 까지 번호가 붙어 있다.
• M - 산책로의 수. 산책로는 0 부터 M-1 까지 번호가 붙어 있다. 산책로의 번호는 아름다운 정도가 줄어드는 순서이다. 즉, 모든 i(0 ≤ i < M-1)에 대해서 산책로 i 는 산책로 i+1 보다 더 아름답다.
• P - 고급 식당이 위치하는 연못의 번호
• R - 산책로들을 표현한 2 차원 배열. 산책로 i(0 ≤ i < M-1)는 연못 R[i][0]과 연못 R[i][1]을 연결한다. 한 산책로는 서로 다른 두개의 연못을 연결하며, 두 연못 사이에는 최대 하나의 산책로만 존재한다는 것에 주의하라.
• Q – 반의 수
• G – 각 반에 대한 K 의 값을 가지는 배열. 각 i(0 ≤ i < Q)에 대해서 G[i]의 값은 반 i 가 목적지 P 에 도달하기 위해 이용하는 산책로의 개수인 K 의 값이다.

각 i(0 ≤ i < Q)에 대해서 당신의 함수는 철수와 반 i 의 학생들이 정확히 G[i]개의 산책로를 이용한 후 연못 P 에 도달할 수 있는 모든 가능한 서로 다른 경로들의 개수를 찾아야 한다. 각 반 i 에 대해서 당신의 함수는 반 i 의 경로의 수가 X 라는 의미로 answer(X)를 호출해야 한다. answer() 함수가 호출되는 순서는 배열 G 에 주어진 순서와 동일해야 한다. 어떤 반에 대해 가능한 경로가 없는 경우는 answer(0)을 호출해야 한다.

첫째 줄에 N, M, P가 주어진다. 다음 M개 줄에는 R[i][0]과 R[i][1]이 주어진다. 다음 줄에는 Q가 주어지며, 그 다음 Q개 줄에는 G[i]가 주어진다.

문제에는 answer(X)를 호출하라고 되어 있지만, answer 함수를 호출하지 말고, X값을 한 줄에 하나씩 순서대로 출력한다.