#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
int n,m,k,tot;
vector<int> edg[MAXN],grp[MAXN<<1];
int dfn[MAXN],low[MAXN],st[MAXN],top,cnt;
int siz[MAXN<<1];
void tarjan(int u){
	st[++top]=u;dfn[u]=low[u]=++cnt;
	for(int v:edg[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				tot++;
				auto add=[&](int u){
					grp[u].push_back(tot);
					grp[tot].push_back(u);
				};
				add(u);
				while(st[top+1]!=v) add(st[top--]);
			}
		}else low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u,int fa,int lim){
	siz[u]=(u<=n);
	for(int v:grp[u]) if(v!=fa){
		dfs(v,u,lim);
		siz[u]+=siz[v];
	}
	if(u<=n&&siz[u]==lim) siz[u]=0,cnt++;
}
void solve_0(){
	int ans=0;
	for(int i=1;i<n;i++) if(n%i==0){
		cnt=0;
		dfs(1,0,i);
		ans+=(cnt>=n/i);
		if(cnt==n/i) cout<<i<<endl; 
	}
	cout<<ans<<endl;
}
void solve_1(){
	
}
int main(){
	ios::sync_with_stdio(false);
//	freopen("ex_cities2.in","r",stdin);
	cin>>n>>m>>k;tot=n;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		edg[u].push_back(v);
		edg[v].push_back(u);
	}
	tarjan(1);
	for(int i=1;i<=n;i++) for(int j:grp[i]) cout<<i<<' '<<j<<endl;
	if(k==0) solve_0();
	else solve_1();
}