#include<bits/stdc++.h> #define ll long long #define PII pair<int,int> #define fi first #define se second using namespace std; const int N=220,M=3e5+10,mod=1e9+7; int n,m,t; struct mat{ bitset<N> v[N]; mat operator*(const mat &b) const{ mat res,tmp; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ tmp.v[i].set(j,b.v[j].test(i)); } }for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) res.v[i].set(j,(v[i]&tmp.v[j]).any()); } return res; } bool operator==(const mat &b) const{ for(int i=1;i<=n;i++){ if(v[i]!=b.v[i]) return 0; }return 1; } }; mat qp(mat a,int b){ mat res=a;b--; while(b){ if(b&1) res=res*a; b>>=1;a=a*a; }return res; } int dfn[M],low[M],sc=0,dc=0,ins[M];stack<int> s; vector<int> e[M];int bel[M]; void tj(int u){ dfn[u]=++dc;low[u]=dc; s.push(u);ins[u]=1; for(auto v:e[u]){ if(!dfn[v]){ tj(v);low[u]=min(low[u],low[v]); }else if(ins[v]){ low[u]=min(low[u],dfn[v]); } }if(low[u]==dfn[u]){ ++sc; while(!s.empty()){ int p=s.top();s.pop(); ins[p]=0; bel[p]=sc;if(p==u) break; } } }bool vis[M]; int gcd(int a,int b){ if(min(a,b)==0) return max(a,b); return gcd(min(a,b),abs(a-b)); } int pg=0;int dist[M]; void dr(int u,int fa){ dist[u]=dist[fa]+1;vis[u]=1;//cout<<bel[u]<<' '<<u<<' '<<dist[u]<<endl; for(auto v:e[u]){ if(bel[u]!=bel[v]) continue; if(vis[v]) pg=gcd(pg,abs(dist[u]+1-dist[v])); else dr(v,u); } } map<int,int> q; void in(int num){ for(int i=2;i<=num;i++){ if(num%i==0){ int cnt=0; while(num%i==0) cnt++,num/=i; //cout<<cnt<<endl; q[i]=max(q[i],cnt); } } }int qp(int a,int b){ int res=1; while(b){ if(b&1) res=1ll*a*res%mod; b>>=1;a=1ll*a*a%mod; }return res; }int lcm(){ int res=1; for(auto it:q){ res=1ll*qp(it.first,it.second)*res%mod; }return res; }int k,d; void slv1(){ for(int i=1;i<=n;i++) if(!dfn[i]) tj(i); for(int i=1;i<=n;i++) if(!vis[i]) dr(i,0),in(pg),pg=0; d=lcm(); } mat st; void wtln(bitset<N> a){ for(int i=1;i<=n;i++) cout<<a.test(i)<<' ';cout<<endl; } void slv2(){ int l=1,r=N*N*10; while(l<r){ int mid=(l+r)/2; if(qp(st,mid+d)==qp(st,mid)) r=mid; else l=mid+1; }k=l; } int main(){ //freopen("lost.in","r",stdin); //freopen("lost.out","w",stdout); cin>>n>>m>>t;if(t==1) for(int i=1;i<=n;i++) st.v[i].reset(); for(int i=1;i<=m;i++){ int u,v;cin>>u>>v;if(t==1) st.v[u].set(v,1); e[u].push_back(v); } //for(int i=1;i<=n;i++) wtln(sa.v[i]); slv1();if(t==1) slv2(),cout<<k<<' ';cout<<d; }