#3792. 跑步

题目描述

小白非常喜欢跑步，所以他经常在校园内跑步（其实是想看美女~）。校园可以看成由N个地区，由M个道路连接。我们小白早上从一个地点出发，但是不知道怎么跑才好。小白有个习惯，不会沿着刚刚经过的道路再返回（比如从A到B经过C道路，下一次，不会再沿着C从B返回A）。
小白想知道从他出发的地点，经过Q条路，到达每个点的方案数。这样方便他去选择。

输入格式

第一行3个整数N,M,S,Q。表示有N个地区，M条道路，从S出发，需要经过Q条路。
下面M行，每行两个整数表示A，B之间有条道路。

输出格式

一共N行，每行一个整数表示从S到I的方案数（mod 45989）

样例

样例输入

10 20 9 10  

1 5  

5 10  

10 4  

10 2  

10 7  

4 3  

10 9  

2 8  

5 6  

6 1  

2 10  

4 7  

9 10  

9 6  

7 3  

7 3  

7 2  

1 8  

9 7  

4 5

样例输出

17420  

41928  

35701  

40814  

31937  

22933  

5754  

15848  

43620  

10819  

数据范围与提示

N<=30 M<=60 Q<=10^16