Description

植物学家 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)。

Input

Output

Sample Input

Sample Output

Hint

Source