1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)23 #define mod 4598924 using namespace std;25 inline ll read()26 {27     ll x=0,f=1;char ch=getchar();28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30     return x*f;31 }32 int n,m,s,tot,cnt,num[maxn],c[maxn][2];33 struct matrix34 {35     int d[maxn][maxn];36     matrix(){memset(d,0,sizeof(d));}37 }a,b;38 inline matrix operator *(matrix &x,matrix &y)39 {40     matrix z;41     for1(i,m)42      for1(j,m)43       for1(k,m)44        (z.d[i][j]+=x.d[i][k]*y.d[k][j])%=mod;45     return z;46 }47 inline void print(matrix x)48 {49     for1(i,m)for1(j,m)cout<<i<<‘ ‘<<j<<‘ ‘<<x.d[i][j]<<endl;50 }51 void ksm(ll y)52 {53     for(;y;y>>=1,a=a*a)54      if(y&1)b=b*a;55 }56 int main()57 {58     freopen("input.txt","r",stdin);59     freopen("output.txt","w",stdout);60     n=read();m=read();s=read();ll q=read();tot=1;61     for1(i,m)62     {63         int x=read(),y=read();64         c[++tot][0]=x;c[tot][1]=y;65         c[++tot][0]=y;c[tot][1]=x;66     }67     m=tot;68     for1(i,m)for1(j,m)if(i!=j&&i!=(j^1)&&c[i][1]==c[j][0])a.d[i][j]=1;69     for1(i,m)b.d[i][i]=1;70     ksm(q-1);71     for1(i,m)if(c[i][0]==s)num[++cnt]=i;72     for1(i,n)73     {74         int ans=0;75         for1(j,m)if(c[j][1]==i)76         for1(k,cnt)(ans+=b.d[num[k]][j])%=mod;77         printf("%d\n",ans);78     }79     return 0;80 }