#include<bits/stdc++.h> using namespace std; #define ll 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=60,inf=1000000000,Mod=1011451423,Mod2=998244853,base=131,base2=2333,Mod1=1000000007; int n,m,q,t,a[MAXN]; struct matrix{ int p[MAXN][MAXN],x,y; pii Hsh(){ pii res={0,0}; for(int i=0;i<x;i++){ for(int j=0;j<y;j++){ res.fr=(res.fr*base+p[i][j])%Mod; res.sc=(res.sc*base2+p[i][j])%Mod2; } } return res; } matrix operator*(const matrix&G)const{ matrix res;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; } }P,K; map<pii,int>mp; void slv(){ n=read(),m=read(),t=read(); P.x=P.y=n; for(int i=1;i<=m;i++){ int u=read(),v=read(); P.p[u-1][v-1]=1; } K=P; mp[P.Hsh()]=1; int c=clock(); for(int i=2;i<=inf;i++){ P=P*K; pii tmp=P.Hsh(); if(!mp[tmp])mp[tmp]=i; else { if(t==1)printf("%d %d",mp[tmp],i-mp[tmp]); else printf("%d",i-mp[tmp]); } } } signed main(){ slv(); return 0; }