열대 식물원

식물학자 철수는 여러 반의 학생들과 함께 거대한 열대 식물원을 방문한다. 이 식물원은 $0$번부터 $N-1$번까지 번호가 붙은 $N$개의 연못과, $0$번부터 $M-1$번까지 번호가 붙은 $M$개의 산책로로 이루어져 있다. 각 산책로는 서로 다른 두 연못을 연결하며 양방향으로 오갈 수 있다. 모든 연못에는 최소한 하나의 산책로가 연결되어 있고, 어떤 두 연못 사이에도 산책로는 많아야 하나뿐이다.

산책로의 번호는 아름다운 정도가 큰 순서대로 매겨져 있다. 즉 모든 $i\ (0 \le i < M-1)$에 대해 산책로 $i$는 산책로 $i+1$보다 더 아름답다. 철수는 식물학자여서 두 산책로의 아름다움이 완전히 같은 경우는 없다.

철수와 학생들은 다음 규칙으로 이동한다. 현재 있는 연못에서는 언제나 가장 아름다운 산책로를 골라 이동한다. 다만 그 산책로를 바로 직전 이동에서 사용했다면, 대신 두 번째로 아름다운 산책로를 사용한다. 단, 현재 연못에 연결된 산책로가 하나뿐이라면 두 번째 산책로가 없으므로 방금 사용한 산책로를 그대로 다시 사용한다. (출발할 때에는 아직 사용한 산책로가 없으므로 항상 가장 아름다운 산책로로 출발한다.)

이 이동 규칙은 결정적이다. 즉, 출발 연못 하나를 정하면 이후의 경로가 유일하게 정해진다.

학생들은 연못 $P$ 옆의 고급 식당에서 점심을 먹고 싶어 한다. 각 반은 정확히 $K$개의 산책로를 지난 뒤 배가 고파지며, 그 순간 반드시 연못 $P$에 도착해 있어야 한다. 반마다 $K$ 값은 다를 수 있다.

$N$개의 연못을 각각 출발점으로 삼을 수 있을 때, 정확히 $K$개의 산책로를 이용한 뒤 연못 $P$에 도착하는 서로 다른 경로가 몇 개인지 구하여라. 각 출발 연못은 유일한 경로 하나를 만들므로, 이는 곧 그러한 출발 연못의 개수와 같다. 도중에 연못 $P$를 지나쳐도 되지만, $K$번째 산책로를 지난 직후에는 반드시 $P$에 있어야 한다.

$Q$개의 반, 즉 $Q$개의 $K$ 값 각각에 대해 답을 구한다.

첫째 줄에 세 정수 $N$, $M$, $P$가 공백으로 구분되어 주어진다.

다음 $M$개의 줄 중 $i$번째 줄($0 \le i < M$)에는 산책로 $i$가 연결하는 두 연못의 번호가 주어진다. 산책로는 아름다운 순서대로, 즉 더 아름다운 산책로가 먼저 주어진다.

그다음 줄에는 반의 수 $Q$가 주어지고, 이어지는 $Q$개의 줄에는 각 반의 $K$ 값이 한 줄에 하나씩 주어진다.

각 반에 대해, 정확히 $K$개의 산책로를 이용하여 연못 $P$에 도착하는 서로 다른 경로(출발 연못)의 개수를 한 줄에 하나씩 입력 순서대로 출력한다. 가능한 경로가 없으면 $0$을 출력한다.