Problem : 261 - Garden

Problem Statistics

Solved Member: 9　　Submission: 96　　User Tried: 13

Statement:

植物學家Somhed經常帶領數群學生們一起前往泰國最大的熱帶花園。此花園的景色是由N 個噴泉（編號為0、1、2、…⋯、N-1）和 M 個步道組成。每一條步道連接兩個相異的噴泉，並且可以依照任意方向進行遊覽。每一個噴泉皆可以由至少一條步道離開。這些步道上皆有Somhed希望觀賞的美麗熱帶植物。每一群學生可以由任何一個噴泉開始他們的行程。

Somhed熱愛美麗的熱帶植物，因此，在任何噴泉時，他和他的學生總會選擇最美麗且可以離開該噴泉的步道，除非其為剛剛走過的步道(僅考慮上一步的移動)並且還有其他的替代步道，在此種狀況下，他們就會選擇第二美麗的步道作為替代方案。當然，如果沒有任何替代方案時，他們會循著相同的步道往回走。注意，由於Somhed是專業的植物學家，對他而言，沒有任何兩條步道是一樣美麗的。

他的學生對於植物並不十分感興趣。然而，他們非常希望可以在噴泉 P 旁的高檔餐廳享用午餐。Somhed知道他的學生們在走過剛好 K 條步道後就會肚子餓，而且每一群學生都有不同的 K 值。在這樣的前提下，Somhed想知道在滿足下列的條件下，各有多少不同的路徑可以選擇給每一群學生：

　• 每一群學生可以由任何一個噴泉出發；
　• 接續步道的決定，必須依照上述的方法；
　• 每一群學生必須在剛好行走 K 條步道後到達編號為 P 的噴泉。

注意：學生們可能會在路徑中提早經過噴泉 P，但是他們仍然需要在噴泉 P 完成他們的路徑。

Task:

給定噴泉和步道的資訊，你必須針對 Q 群學生各自的 K 值，找到正確的答案。

　• N – 噴泉的數目。這些噴泉的編號為 0 至 N-1。
　• M – 步道的數目。這些步道的編號為 0 至 M-1。其編號大小和其美麗程度相反。對於 0 ≤ i < M-1，步道 i 比步道 i+1 美麗。
　• P – 高檔餐廳所在地之噴泉
　• Q – 學生群的數目。
　• Gi –代表第 i 群學生所行走的步道數目( K )。

你的程式必須找到所有可能的路徑數目，讓第i群學生可以剛好在走過Gi 條步道後抵達噴泉 P。

對於每一群學生，你的程式必須輸出一個數字X於一行，表示路徑的數目為 X。

這些答案必須依照和學生群編號相同的順序回答。如果沒有任何合法的路徑，你的程式必須輸出0。

Input:Output:

第一行有三個數字N M P。

接下來有M行，每行兩個數字，表示每條步道所連接的相異噴泉。

接下來的一行是數字Q，表示學生群的數目。

接下來的一行有Q個以空白隔開的數字Gi。

對於每一群學生，你的程式必須輸出一個數字X於一行，表示路徑的數目為 X。

這些答案必須依照和學生群編號相同的順序回答。如果沒有任何合法的路徑，你的程式必須輸出0。

Subtask 1 (49 points)
　•2 ≤ N ≤ 1000
　•1 ≤ M ≤ 10000
　•Q = 1
　•1 ≤ Gi ≤ 100
Subtask 2 (20 points)
　•2 ≤ N ≤ 150000
　•1 ≤ M ≤ 150000
　•Q = 1
　•1 ≤ Gi ≤ 1000000000
Subtask 3 (31 points)
　•2 ≤ N ≤ 150000
　•1 ≤ M ≤ 150000
　•1 ≤ Q ≤ 2000
　•1 ≤ Gi ≤ 1000000000

Sample Input:Sample Output:

Sample #1:
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3

Sample #2:
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1

Sample #1:
2

Sample #2:
1
2

HINT:

測資3d, 3f, 3g時限放寬為10s @ 2013/5/27 16:39 by hanhan0912
子測資3時限縮短為2s @ 2013/7/24 23:56 by hanhan0912

Source:

IOI 2011

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
1-1	1000ms	262144kb	49
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
1-5	1000ms	262144kb
1-6	1000ms	262144kb
1-7	1000ms	262144kb
1-8	1000ms	262144kb
1-9	1000ms	262144kb
2-1	2000ms	262144kb	20
2-2	2000ms	262144kb
2-3	2000ms	262144kb
2-4	2000ms	262144kb
2-5	2000ms	262144kb
2-6	2000ms	262144kb
2-7	2000ms	262144kb
2-8	2000ms	262144kb
2-9	2000ms	262144kb
2-10	2000ms	262144kb
2-11	2000ms	262144kb
2-12	2000ms	262144kb
2-13	2000ms	262144kb
2-14	2000ms	262144kb
3-1	2000ms	262144kb	31
3-2	2000ms	262144kb
3-3	2000ms	262144kb
3-4	2000ms	262144kb
3-5	2000ms	262144kb
3-6	2000ms	262144kb
3-7	2000ms	262144kb
3-8	2000ms	262144kb
3-9	2000ms	262144kb
3-10	2000ms	262144kb
3-11	2000ms	262144kb
3-12	2000ms	262144kb
3-13	2000ms	262144kb
3-14	2000ms	262144kb