問題文

ナナは魔法の国に来ています。その国は$N$個の町と$M$本の道から構成されています。道$i\ (1 \leq i \leq M)\$は町$U_i$と$V_i$を双方向に結んでいます。
ナナは$X$日間この魔法の国で冒険することになりました。$i$日目$\ (1 \leq i \leq X)\$では、以下の様に行動します。
・今いる町につながっている道のうち、$1$つの道をランダムに選び、その道を使って移動する。ただし、$2$日目以降は前日に選んだ道は選ばないものとする。また、移動できる道がない場合は、その日は移動しないものとする。
候補にある道のうちどれが選ばれるかは同様に確からしいもの、つまり、等確率とします。$1$日目の移動を行う前は町$1$にいます。
$t=1,2,\ldots,N\$において$X$日目の行動が終わった時にナナが町$t$にいる確率を$\mod 998244353\$で求めてください。つまりそれぞれにおいて、確率は分母が$998244353$と互いに素な既約分数表示を持つ有理数になるので、答えが既約分数で$\frac{p}{q}$となるとき$\ qx=p\pmod{998244353}\$となる整数$x\ (0 \leq x \leq 998244352)\$を求めてください。
この国では同じ町に戻ってきてしまう道や、ある$2$つの町において、その町同士を結ぶ道がたくさんあったり、そもそも、町$1$からいくつかの道を通っても、ある町にたどり着けない場合もあります。つまり、非連結であったり多重辺や自己ループ辺を含む場合があります。

入力

$N\ M \ X$
$U_1 \ V_1$
$U_2 \ V_2$
$\vdots$
$U_M \ V_M$

・$2 \leq N \leq 10$
・$1 \leq M \leq 1000$
・$1 \leq X \leq 10^8$
・$1 \leq U_i,V_i \leq N\ (1 \leq i \leq M)$
・$N,M,X,U_i,V_i\ (1 \leq i \leq M)\$はすべて整数

出力

$N$行出力してください。$i$行目には町$i$にいる確率を出力してください。

サンプル

3 5 2
1 2
1 2
2 2
1 3
3 3

332748118
332748118
332748118

5 5 11
1 2
2 3
3 4
4 5
5 5

0
1
0
0
0

3 2 100000000
1 1
2 2

1
0
0