QAQ 大水题我都不会啊嘤嘤嘤

#include <bits/stdc++.h>

#define REG register
#define MS (125)
#define MOD (45989)
#define pls(a, b) ((a) + (b) >= MOD ? (a) + (b) - MOD : (a) + (b))
#define mul(a, b) ((a) * (b) % MOD)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, s, u[MS], v[MS], cnt, d[MS][MS], res[MS][MS], tmp[MS][MS];

LL q;

inline void M_mul(int (&a)[MS][MS], int (&b)[MS][MS])
{
memset(tmp, 0, sizeof(tmp));
for (REG int k = 0; k < cnt; k += 1)
for (REG int i = 0; i < cnt; i += 1)
for (REG int j = 0; j < cnt; j += 1)
tmp[i][j] = pls(tmp[i][j], mul(a[i][k], b[k][j]));
memmove(a, tmp, sizeof(a));
}

inline void M_qpow(REG LL k)
{
for (REG int i = 0; i < cnt; i += 1) res[i][i] = 1;
while (k)
{
if (k & 1) M_mul(res, d);
M_mul(d, d), k >>= 1;
}
}

int se[MS], sc;

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(s), IN(q);
for (REG int i = 1; i <= m; i += 1)
{
IN(u[cnt]), IN(v[cnt]), cnt++;
u[cnt] = v[cnt - 1], v[cnt] = u[cnt - 1], cnt++;
}
for (REG int i = 0; i < cnt; i += 1)
for (REG int j = 0; j < cnt; j += 1)
if (i != j && i != (j ^ 1) && v[i] == u[j])
d[i][j] = 1;
M_qpow(q - 1);
for (REG int i = 0; i < cnt; i += 1)
if (u[i] == s) se[++sc] = i;
for (REG int i = 1; i <= n; i += 1)
{
REG int ans = 0;
for (REG int j = 0; j < cnt; j += 1)
if (v[j] == i)
for (REG int k = 1; k <= sc; k += 1)
ans = pls(ans, res[se[k]][j]);
printf("%d\n", ans);
}
return 0;
}