植物学者の Somhed は, いくつかの学生グループをタイ最大級の熱帯植物園によく連れて行く. この植物園には N 個の噴水 (0, 1, ..., N－1の番号が付いている) があり, M 本の道で結ばれている. 各々の道は 2 つの異なる噴水を結んでおり, 結んでいる噴水の対はどの道についても異なる. 道はどちら向きにも通行可能である. また, どの噴水にも少なくとも 1 本の道が接続している. Somhed はこれらの道を彩る美しい植物を見たいと思っている. 各々のグループは植物園のどの噴水からでも歩き始めることができる.

Somhed は美しい熱帯植物が大好きなので, 彼と学生たちは現在いる噴水に接続する道のうちもっとも美しい道を選んで移動する. ただし, もっとも美しい道が直前に通った道であり, それ以外にも接続する道がある場合は, 2 番目に美しい道を選ぶ. 直前に通った道のみしか接続している道がない場合は, 今来た道を戻ることになる. Somhed はプロの植物学者なので, 彼にとってどの 2 本の道も同じ美しさではない.

学生たちは植物にはあまり興味がない. かわりに, 噴水 P にある高級レストランで昼食を食べたいと思っている. Somhed は, 学生たちがちょうど K 回の移動の後に腹を空かすということを知っている (ただし, K の値はグループごとに異なるかもしれない). Somhed は, 各々のグループに対し，次の条件をみたす経路がそれぞれどれだけあるのかが気になった:

• どの噴水から歩き始めてもよい.
• 噴水から次にどの噴水へ移動するかは上のように決める.
• ちょうど K 回の移動の後, 噴水 P にいなければならない.

K 回の移動の後に噴水 P にいさえすれば, それ以前に噴水 P を通っていてもよいことに注意せよ.

課題 (Your task)

噴水と道の情報が与えられたとき, Q 個の学生のグループについて (つまり, Q 個の 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 ― 道の情報を表す 2 次元配列. 0 ≦ i < M に対し, 道 i は噴水 R[i][0] と R[i][1] を結んでいる. 各々の道は 2 つの異なる噴水を結んでおり, 結んでいる噴水の対はどの道についても異なることに注意せよ.
• Q ― 学生のグループの個数.
• G ― 各々の学生のグループに対する K の値を表す 1 次元配列. 0 ≦ i < Q に対し, G[i] は i 番目のグループに対する K の値である.

各 0 ≦ i < Q に対し, ちょうど G[i] 回の移動の後に噴水 P にいるような i 番目のグループの経路の個数 X を計算し, answer(X) を呼び出せ. 呼び出す順番はグループの順番と対応していなければならない. ただし条件をみたす経路がない場合は answer(0) を呼び出せ.

例 (Examples)

例 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 回の移動からなる可能な経路は次の 2 通りのみである.

• 1 → 2 → 1 → 0
• 5 → 4 → 3 → 0

最初の経路は噴水 1 から始まる. 彼らはまずそこに接続する最も美しい道を通って噴水 2 へ移動する. 噴水 2 からは道が 1 本しか選べないので, 彼らは同じ道を戻る. 噴水 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

の場合を考える.

1 つ目のグループについて, 3 回の移動の後に噴水 2 にいるような経路は 1 → 0 → 1 → 2 の 1 つしかない.

2 つ目のグループについて, 1 回の移動の後に噴水 2 にいるような経路は 3 → 2 と 4 → 2 の 2 つが考えられる.

よってこの場合, count_routes の正しい実装は, まず最初のグループ ( 0 番目のグループ) に対応する回答として answer(1) を呼び出し, それから次のグループ ( 1 番目のグループ) に対応する回答として answer(2) を呼び出さなければならない.

小課題 (Subtasks)

小課題 1 (49 点)

• 2 ≦ N ≦ 1 000
• 1 ≦ M ≦ 10 000
• Q = 1
• G の各要素は 1 以上 100 以下の整数である.

小課題 2 (20 点)

• 2 ≦ N ≦ 150 000
• 1 ≦ M ≦ 150 000
• Q = 1
• G の各要素は 1 以上 1 000 000 000 以下の整数である.

小課題 3 (31 点)

• 2 ≦ N ≦ 150 000
• 1 ≦ M ≦ 150 000
• 1 ≦ Q ≦ 2 000
• G の各要素は 1 以上 1 000 000 000 以下の整数である.

実装の詳細 (Implementation details)

制限 (Limits)

• CPU 時間制限 (CPU time limit): 5 秒
• メモリ制限 (Memory limit): 256 MB
注意: スタックのサイズには決められた制限はない. スタックとして使用されたメモリは, メモリ総使用量に含まれる.

インターフェース (API) (Interface (API))

• 実装フォルダ (Implementation folder): garden/
• 選手が実装するファイル: garden.c または garden.cpp または garden.pas
• 提出ファイルのインターフェース (Contestant interface): garden.h または garden.pas
• 採点プログラムのインターフェース (Grader interface): gardenlib.h または gardenlib.pas
• 採点プログラムのサンプル (Sample grader): grader.c または grader.cpp または grader.pas
• 採点プログラムの入力のサンプル (Sample grader input): grader.in.1, grader.in.2, ...
  注意: 採点プログラムのサンプルは次の書式の入力を読み込む.
  • 1 行目: N, M, P.
  • 2 行目から M＋1 行目: 道の情報. つまり, 0 ≦ i < M に対し, i＋2 行目には R[i][0], R[i][1] が空白区切りで書かれている.
  • M＋2 行目: Q.
  • M＋3 行目: G (空白で区切られた整数の列).
  • M＋4 行目: 期待される解 (空白で区切られた整数の列).
• 採点プログラムの入力のサンプルに対して, 期待される出力: grader.expect.1, grader.expect.2, ...
  この課題において, これらのファイルはいずれも文字列 “Correct.” のみを含むファイルである.