#3792. 跑步

内存限制:256 MiB 时间限制:10 Sec

题目描述

小白非常喜欢跑步,所以他经常在校园内跑步(其实是想看美女~)。校园可以看成由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