#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define pb push_back #define inx(u) int I=h[u],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define pii pair<ll,ll> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c==EOF)return -1;if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} const int MAXN=200010,N=210,inf=1000000000,Mod=1000000007; int Pow(int x,int y){int res=1;while(y){if(y&1)res=res*x%Mod;x=x*x%Mod,y>>=1;}return res;} struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT=1;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int n,m,t,a[MAXN]; struct matrix{ int p[N][N],x,y; void init(int o){memset(p,0,sizeof(p));x=y=o;} matrix operator*(const matrix&G)const{ matrix res;res.init(x); res.x=x,res.y=G.y; for(int i=0;i<x;i++){ for(int j=0;j<G.y;j++){ res.p[i][j]=0; for(int k=0;k<y;k++){ res.p[i][j]|=p[i][k]&G.p[k][j]; } } } return res; } bool operator ==(const matrix&G)const{ for(int i=0;i<x;i++){ for(int j=0;j<y;j++)if(p[i][j]!=G.p[i][j])return 0; } return 1; } void prt(){ for(int i=0;i<x;i++){ for(int j=0;j<y;j++)cout<<p[i][j]<<" "; cout<<endl; } cout<<endl; } }P,K; matrix PPow(matrix x,int y){y--; matrix res=x; while(y){ if(y&1)res=res*x; x=x*x,y>>=1; } return res; } int dfn[MAXN],low[MAXN],cnt,stk[MAXN],dep[MAXN],bel[MAXN],p[MAXN],k; stack<int>st; void dfs(int u){ dfn[u]=low[u]=++cnt; st.push(u),stk[u]=1; for(inx(u)){ if(stk[v]){ low[u]=min(low[u],dfn[v]); } else if(!dfn[v]){ dfs(v); low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){ while(st.top()!=u){ bel[st.top()]=u,stk[st.top()]=0,st.pop(); } bel[st.top()]=u,stk[st.top()]=0,st.pop(); } } int gcz(int x,int y){ return !x||!y?x|y:gcz(y%x,x); } void dfs2(int u,int ty){ for(inx(u))if(bel[v]==ty&&!dep[v]){ dep[v]=dep[u]+1; dfs2(v,ty); } else if(bel[v]==ty){ a[ty]=gcz(a[ty],abs(dep[u]+1-dep[v])); } } int lcm[MAXN]; bool check(int x){ matrix res=PPow(P,x); return res*K==res; } void slv(){ n=read(),m=read(),t=read();P.init(n); for(int i=1;i<=m;i++){ int u=read(),v=read(); add_side(u,v); if(t)P.p[u-1][v-1]=1; } for(int i=1;i<=n;i++)if(!dfn[i])dfs(i); for(int i=1;i<=n;i++)if(bel[i]==i)dep[i]=1,dfs2(i,i),p[++k]=a[i],cout<<p[k]<<" ";cout<<endl; for(int i=1;i<=k;i++){ for(int j=2;j*j<=p[i];j++){ int tmp=0; while(p[i]%j==0)tmp++,p[i]/=j; lcm[j]=max(lcm[j],tmp); } if(p[i]!=1)lcm[p[i]]=max(lcm[p[i]],1ll); } int ans=1; for(int i=2;i<=n;i++)ans=ans*Pow(i,lcm[i])%Mod; K=P; for(int i=2;i<=n;i++)K=PPow(K,Pow(i,lcm[i])); if(t==1){ int l=1,r=40000; while(l<r){ int mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } printf("%lld ",l); } printf("%lld",ans); } signed main(){ slv(); // fclose(stdin);fclose(stdout); return 0; }