植物学家 Somhed 经常带领学生前往泰国最大的热带花园之一。 该花园的景观由 $N$ 个喷泉（编号为 $0, 1, \dots, N-1$）和 $M$ 条路径组成。 每条路径连接一对不同的喷泉，且可以在两个方向上通行。 每个喷泉至少有一条路径与之相连。这些路径上有着 Somhed 想要参观的精美植物收藏。每个小组可以从任意喷泉开始他们的旅程。

Somhed 热爱美丽的植物。因此，从任何喷泉出发，他和他的学生都会选择离开该喷泉最美丽的路径，除非这条路径是他们刚刚走过的路径，且存在另一条可选路径。在这种情况下，他们会选择第二美丽的路径。当然，如果没有其他选择，他们将原路返回，第二次走同一条路径。请注意，由于 Somhed 是一位专业的植物学家，对他而言，没有两条路径的优美程度是相同的。

他的学生对植物不太感兴趣。然而，他们很想在位于 $P$ 号喷泉旁边的顶级餐厅吃午餐。Somhed 知道，他的学生在走过恰好 $K$ 条路径后会感到饥饿，其中 $K$ 对于每个学生小组可能不同。 Somhed 想知道对于每个小组，他可以选择多少种不同的路线，前提是： 每个小组可以从任意喷泉开始； 后续路径必须按照上述方式选择； * 每个小组必须在走过恰好 $K$ 条路径后到达 $P$ 号喷泉。

请注意，他们可能会在路线中途经过 $P$ 号喷泉，但他们仍需在走完 $K$ 条路径时结束于 $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$ 个小组为了到达喷泉 $P$ 而可能采取的恰好走过 $G[i]$ 条路径的路线数量。对于每个小组 $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

图 1。

注意，路径按优美程度递减列出。即路径 0 是最美的，路径 1 是第二美的，依此类推。 只有两条可能的有效路线走过 3 条路径： $1 \to 2 \to 1 \to 0$，以及 $5 \to 4 \to 3 \to 0$。

第一条路线从喷泉 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

图 2。

对于第一个小组，只有一条有效路线在走过 3 条路径后到达喷泉 2：$1 \to 0 \to 1 \to 2$。 对于第二个小组，有两条有效路线在走过 1 条路径后到达喷泉 2：$3 \to 2$ 和 $4 \to 2$。 因此，count_routes 的正确实现应首先调用 answer(1) 来报告第一个小组的答案，然后调用 answer(2) 来报告第二个小组的答案。

子任务

子任务 1 (49 分)

• $2 \le N \le 1\,000$
• $1 \le M \le 10\,000$
• $Q = 1$
• $G$ 的每个元素是 $1$ 到 $100$ 之间的整数（包含边界）。

子任务 2 (20 分)

• $2 \le N \le 150\,000$
• $1 \le M \le 150\,000$
• $Q = 1$
• $G$ 的每个元素是 $1$ 到 $1\,000\,000\,000$ 之间的整数（包含边界）。

子任务 3 (31 分)

• $2 \le N \le 150\,000$
• $1 \le M \le 150\,000$
• $1 \le Q \le 2\,000$
• $G$ 的每个元素是 $1$ 到 $1\,000\,000\,000$ 之间的整数（包含边界）。