[IOI2011]garden

内存限制：128 MiB 时间限制：10 Sec

植物学家 Somhed 带着几组学生去泰国最大的热带花园游玩。这个花园中有 N 个喷泉（编号为0, 1, …, N-1）和 M 条小路。每条小路连接一对不同的喷泉，两个喷泉间最多只有一条小路，小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽程度决定了Somhed 选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。在任何一个喷泉，Somhed 和他的学生们会选择最美丽的一条小路离开该喷泉，除非最美丽的这条小路是他们刚刚走过的，且还有其它小路可走。在这种情况下，他们会选择第二美丽的小路离开该喷泉。当然，如果没有第二美丽的小路可选，他们会选择刚刚走过的小路
再走回去。注意，对于Somhed 来说没有两条小路是同样美丽的。
Somhed 的学生们对小路的美丽与否不感兴趣，他们喜欢在喷泉 P 旁边的豪华餐厅吃午饭。Somhed 知道他的学生在走过恰好 K 条小路后会感觉饥饿，当然，对于不同组的学生K 可以不同。Somhed 想知道在下列条件下，对于每组学生有多少条不同的路径可选。
每组可以从任意喷泉出发；
但是接下来的路径必须按照上面描述的规则进行选择；
每组必须在恰好走过 K 条小路后到达喷泉 P 。

注意：他们在最终到达喷泉P之前可能曾经到过喷泉 P。
给定喷泉和小路的信息，以及 Q 个不同的 K，你要回答对于每个 K 来说, 有多少条不同的
路径可供候选。
写一个函数count_routes(N,M,P,R,Q,G)，该函数的参数如下：
N – 喷泉的数目。喷泉从 0 到 N-1 编号。
M – 小路的数目。小路从 0 到 M-1编号。所有小路按照其美丽程度从大到小的
顺序给出，即对于 0 ≤ i < M-1, 小路 i 比小路 i+1 更美丽。
P – 豪华餐厅所在的喷泉编号。
R – 描述小路的二维数组。对于 0 ≤ i < M, 小路 i 连接喷泉 R[i][0] 和喷泉
R[i][1]。再次提醒：每条小路连接两个不同的喷泉，两个喷泉间最多只有一条小
路。
Q – 学生的组数。
G – 一个一维的整数数组，包含 Q 个不同的 K。对于 0 ≤ i < Q，G[i]表示第i 组
学生对应的K，即第 i 组学生经过K 条小路后要到达喷泉P。
对于 0 ≤ i < Q，你的函数必须给出可能的路径数目，满足第i 组学生在到达喷泉 P 时恰好
走过 G[i]条小路。对于第 i 组学生，你的函数必须调用函数 answer(X) 来给出可能的路径的
数目 X。答案给出的顺序必须和问题给出的顺序相同。如果没有合适的路径，你的函数应该
调用 answer(0)。

样例输入

#2598. [IOI2011]garden

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示