TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

100.0% (16/16)

Submission's AC Ratio

60.8% (59/97)

Tags

Description

在某個小島上,有n個城市(編號為0到n-1)用m條單向道路連結。然而為了疏運,從一個城市出發到另一個城市之間可能會連有許多條單向道路,也可能會有從某個城市出發回到同一個城市的道路(這樣才不會塞車塞得太無聊)。

冥銋,剛當上警察,意氣風發的程式設計師(咦),正試圖分析著小島上搶劫案經過的模式。為此,他找來了$Q$起已偵結的搶劫案,試圖從中摸索出一個搶劫犯應該會具有的紳士風度。然而這些紀錄並不完全,只記錄了$(a_i, b_i)$,其中$a_i$是搶劫案發生的城市,$b_i$是搶匪遭到逮捕的城市,而且這些搶案有個共同之處:搶匪在逃亡過程經過的邊數皆恰為$L$(如果某條邊被經過多次,那麼他對$L$的貢獻會重複計算)。冥銋想要走過所有可能的路徑,但是憑他一己之力實在很難在短時間內暴搜完所有可能路徑。好險,身為一個程式設計師,他還會「多重影分身之術」(一種將多執行緒實現於現實(?)的演算法),所以可以同時探索多條路徑。

然而,要知道,「多重影分身之術」是非常消耗查克拉…呃…我是說…CPU的。所以冥銋想製造出和路徑可能總數一樣多的影分身,讓他可以在最短的時間耗最少的CPU完成他的任務。雖然他是一名很厲害的程式設計師,不過他還必需要準備多重影分身之術的執行,所以他將計算出路徑可能總數的任數交給了你。

Input Format

第一行含有四個正整數$n\leq 150,m\leq 10^ 6,Q\leq 20000, L\leq 10^ 9$,代表城市個數,單向道路個數、案件個數以及過程中搶匪經過的邊數(重複計算)。
接下來的$m$行,每行含有兩個整數$0\leq s_i, e_i\leq n-1$,代表有一條道路從第$s_i$號城市到第$e_i$城市。
接下來的$Q$行,每行含有兩個整數$0\leq a_i, b_i \leq n-1$,分別代表這起搶劫案的發生地點以及搶匪落網的地點。

子任務(測資) 額外限制 分數
1 (0~2) $L\leq 30$ 40
2 (0~4) 無限制 60

Output Format

對於每起搶案,請輸出可能路徑的個數。由於答案可能很大,請將答案模1000000009後輸出。

Sample Input

4 7 2 2
0 1
1 2
0 3
3 2
0 2
0 2
0 0
0 2
2 0

Sample Output

4
0

Hints

對於第一種案件:
0→1→2一種
0→3→2一種
0→0→2兩種

Problem Source

Problem set / Description by Paupière

Subtasks

For Testdata: 0 ~ 2, Score: 40
For Testdata: 0 ~ 4, Score: 60
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1500 65536 65536
4 1500 65536 65536