说明

植物学家 Somhed 定期带领学生团体参观泰国最大的热带花园之一。这个花园的景观由 $N$ 个喷泉（编号为 $0, 1,\ldots, N-1$）和 $M$ 条小径组成。每条小径连接一对不同的喷泉，并且可以双向通行。每个喷泉至少有一条小径离开。这些小径沿途有 Somhed 想要欣赏的美丽植物收藏。每个团体可以从任意喷泉开始他们的行程。

Somhed 热爱美丽的热带植物。因此，从任何一个喷泉出发，他和他的学生们会走离开该喷泉的最美丽的小径，除非这条小径是刚刚走过的并且有另一条可选。在这种情况下，他们会改走第二美丽的小径。当然，如果没有可选的小径，他们会原路返回，第二次使用同一条小径。注意，由于 Somhed 是专业植物学家，对他来说没有两条小径是同样美丽的。

他的学生们对植物不太感兴趣。不过，他们非常想在位于编号为 $P$ 的喷泉旁的顶级餐厅吃午餐。Somhed 知道他的学生们会在恰好走了 $K$ 条小径后感到饥饿，$K$ 的值可能因学生团体而异。Somhed 想知道他可以为每个团体选择多少条不同的路线，给定以下条件：

• 每个团体可以从任意喷泉出发；
• 连续选择的小径必须按照上述方式；
• 每个团体必须在恰好走了 $K$ 条小径后，在 $P$ 号喷泉结束。

注意，他们可以在路线中提前经过 $P$ 号喷泉，尽管他们仍然需要在 $P$ 号喷泉结束路线。

交互细节

根据给出的喷泉和小径信息，你需要为 $Q$ 个学生团体找出答案；也就是说，为 $Q$ 个 $K$ 的值找出答案。

编写一个过程 count_routes(N, M, P, R, Q, G)，它接受以下参数：

• $N$ - 喷泉的数量。喷泉编号为 $0$ 到 $N-1$。
• $M$ - 小径的数量。小径编号为 $0$ 到 $M-1$。小径将按美丽程度降序给出：对于 $0 \le i < M-1$，小径 $i$ 比小径 $i+1$ 更美丽。
• $P$ - 顶级餐厅所在的喷泉。
• $R$ - 一个表示小径的二维数组。对于 $0 \le i < M$，小径 $i$ 连接喷泉 $R[i][0]$ 和 $R[i][1]$。回想一下，每条小径连接一对不同的喷泉，并且没有两条小径连接同一对喷泉。
• $Q$ - 学生团体的数量。
• $G$ - 一个包含 $K$ 值的一维整数数组。对于 $0 \le i < Q$，$G[i]$ 是第 $i$ 个团体将要走的路径数量 $K$。

对于 $0 \le i < Q$，你的过程必须找出第 $i$ 个团体可能采取的、恰好有 $G[i]$ 条小径且能到达 $P$ 号喷泉的路线数量。对于每个团体 $i$，你的过程应该调用过程 answer(X) 来报告路线数量为 $X$。答案必须按团体的相同顺序给出。如果没有有效路线，你的过程必须调用 answer(0)。

交互示例

示例 1

考虑图 1 所示的情况，其中 $N=6, M=6, P=0, Q=1, G[0]=3$，并且 $R=$

1 2
0 1
0 3
3 4
4 5
1 5

注意小径是按美丽程度递减列出的。也就是说，小径 $0$ 是最美丽的，小径 $1$ 是第二美丽的，依此类推。

只有两条可能的有效路线能恰好走 $3$ 条小径：

$1\to2\to1\to0$，以及

$5\to4\to3\to0$。

第一条路线从喷泉 $1$ 开始。从这里出发的最美丽小径通向喷泉 $2$。在喷泉 $2$ 处，团体别无选择，必须沿同一条小径返回。回到喷泉 $1$ 后，团体现在将避免走小径 $0$，而是选择小径 $1$。这条小径确实将他们带到了 $P=0$ 号喷泉。

因此，该过程应该调用 answer(2)。

示例 2

考虑图 2 所示的情况，其中 $N=5, M=5, P=2, Q=2, G[0]=3, G[1]=1$，并且 $R=$

1 0
1 2
3 2
1 3
4 2

对于第一个团体，只有一条有效路线能在走 $3$ 条小径后到达喷泉 $2$：$1\to0\to1\to2$。

对于第二个团体，有两条有效路线能在走 $1$ 条小径后到达喷泉 $2$：$3\to2$ 和 $4\to2$。

因此，count_routes 的正确实现应该首先调用 answer(1) 来报告第一个团体的答案，然后调用 answer(2) 来报告第二个团体的答案。

输入格式

示例评分器按以下格式读取输入：

• 第 $1$ 行：$N$、$M$ 和 $P$。
• 第 $2$ 行到第 $M+1$ 行：小径的描述；即第 $i+2$ 行包含 $R[i][0]$ 和 $R[i][1]$，以空格分隔，其中 $0 \le i < M$。
• 第 $M+2$ 行：$Q$。
• 第 $M+3$ 行：数组 $G$，为一串空格分隔的整数序列。
• 第 $M+4$ 行：预期解的数组，为一串空格分隔的整数序列。

输出格式

示例评分器输出：对于此任务，这些文件中的每一个都应精确地包含文本 Correct.

提示

数据范围

• 子任务 1 (49 分)
  • $2 \le N \le 1000$
  • $1 \le M \le 10^4$
  • $Q = 1$
  • $G$ 的每个元素是介于 $1$ 和 $100$ 之间的整数（含端点）。
• 子任务 2 (20 分)
  • $2 \le N \le 1.5\times10^5$
  • $1 \le M \le 1.5\times10^5$
  • $Q = 1$
  • $G$ 的每个元素是介于 $1$ 和 $10^9$ 之间的整数（含端点）。
• 子任务 3 (31 分)
  • $2 \le N \le 1.5\times10^5$
  • $1 \le M \le 1.5\times10^5$
  • $1 \le Q \le 2,000$
  • $G$ 的每个元素是介于 $1$ 和 $10^9$ 之间的整数（含端点）。