//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rnd(1919810);
int n=10000,m=200000,k=8;
vector<int> G[10005];
int u[200005],v[200005];
bool used[200005];
bool vis[10005];
map<pii,int> Mp;
int ls[10005],rs[10005],siz[10005];
int fa[10005];
ull prior[10005];
bool tag[10005];
inline void pushdown(int x)
{
	if(tag[x])
	{
		tag[ls[x]]^=1;
		tag[rs[x]]^=1;
		tag[x]=0;
		swap(ls[x],rs[x]);
	}
}
inline void pushup(int x)
{
	fa[ls[x]]=fa[rs[x]]=x;
	siz[x]=siz[ls[x]]+siz[rs[x]]+1;
}
int merge(int x,int y)
{
	if(!x||!y) return x^y;
	if(prior[x]>prior[y])
	{
		pushdown(x);
		rs[x]=merge(rs[x],y);
		pushup(x);
		fa[x]=0;
		return x;
	}
	else
	{
		pushdown(y);
		ls[y]=merge(x,ls[y]);
		pushup(y);
		fa[y]=0;
		return y;
	}
}
void split(int x,int s,int &a,int &b)
{
	if(!x)
	{
		a=b=0;
		return ;
	}
	pushdown(x);
	if(s>=siz[ls[x]]+1)
	{
		a=x;
		split(rs[x],s-siz[ls[x]]-1,rs[a],b);
		pushup(a);
		fa[a]=fa[b]=0;
	}
	else
	{
		b=x;
		split(ls[x],s,a,ls[b]);
		pushup(b);
		fa[a]=fa[b]=0;
	}
}
int findr(int x)
{
	pushdown(x);
	if(rs[x]) return findr(rs[x]);
	return x;
}
int findr2(int x)
{
	pushdown(x);
	if(siz[x]<2) return 0;
	if(siz[rs[x]]>=2) return findr2(rs[x]);
	if(siz[rs[x]]==1) return x;
	return findr(ls[x]);
}
int rt;
inline int getpos(int x)
{
	vector<int> seq;
	seq.pb(x);
	while(seq.back()!=rt)
		seq.pb(fa[seq.back()]);
	rev(seq);
	for(auto xx:seq)
		pushdown(xx);
	int ret=0;
	ret+=siz[ls[x]];
	while(fa[x])
	{
		int tmp=x;
		x=fa[x];
		if(tmp==rs[x])
			ret+=siz[ls[x]]+1;
	}
	return ret;
}
int lst;
void print(int x)
{
	pushdown(x);
	if(ls[x]) print(ls[x]);
	cout<<x<<" ";
	if(rs[x]) print(rs[x]);
}
void printr(int x)
{
	pushdown(x);
	if(ls[x]) printr(ls[x]);
	cerr<<x<<" ";
	if(rs[x]) printr(rs[x]);
}
void clear(int x)
{
	pushdown(x);
	if(ls[x]) clear(ls[x]);
	if(lst!=-1)
		used[Mp[mp(x,lst)]]^=1;
	lst=x;
	if(rs[x]) clear(rs[x]);
}
int main()
{
	// freopen("out.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// for(int i=1;i<=m;i++)
	// {
	// 	int u=rnd()%n+1;
	// 	int v=rnd()%n+1;
	// 	while(u==v) v=rnd()%n+1;
	// 	::u[i]=u;
	// 	::v[i]=v;
	// 	if(u==v||Mp[mp(u,v)])
	// 	{
	// 		used[i]=1;
	// 		continue;
	// 	}
	// 	Mp[mp(u,v)]=Mp[mp(v,u)]=i;
	// }
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i];
		if(u[i]==v[i]||Mp[mp(u[i],v[i])])
		{
			used[i]=1;
			continue;
		}
		Mp[mp(u[i],v[i])]=Mp[mp(v[i],u[i])]=i;
	}
	int Lst=0;
	for(int i=0;i<min(k,8);i++)
	{
		for(int j=1;j<=n;j++)
		{
			fa[j]=0;
			ls[j]=rs[j]=0;
			siz[j]=1;
			prior[j]=rnd();
			tag[j]=0;
		}
		for(int j=1;j<=n;j++)
			G[j].clear();
		memset(vis,0,sizeof(vis));
		for(int j=1;j<=m;j++)
			if(!used[j])
			{
				G[u[j]].pb(v[j]);
				G[v[j]].pb(u[j]);
			}
		int st=rnd()%n+1;
		rt=st;
		vis[st]=1;
		int Cnt=0;
		int Lst=-1;
		while(siz[rt]!=n)
		{
			tag[rt]^=1;
			Cnt++;
			int x=findr(rt);
			int x2=findr2(rt);
			shuffle(ALL(G[x]),rnd);
			if(Cnt>300000)
			{
				break;
			}
			bool fl=0;
			for(auto y:G[x])
			{
				if(!vis[y])
				{
					fl=1;
					Lst=-1;
					vis[y]=1;
					rt=merge(rt,y);
					fa[rt]=0;
					used[Mp[mp(x,y)]]^=1;
					break;
				}
				else if(y!=x2&&y!=Lst)
				{
					fl=1;
					Lst=y;
					int pos=getpos(y);
					int A,B;
					split(rt,pos+1,A,B);
					fa[A]=fa[B]=0;
					tag[B]=1;
					used[Mp[mp(x,y)]]^=1;
					rt=merge(A,B);
					fa[rt]=0;
					used[Mp[mp(findr(rt),y)]]^=1;
					break;
				}
			}
			if(!fl)
				break;
		}
		if(siz[rt]!=n)
		{
			lst=-1;
			clear(rt);
			i--;
			continue;
		}
		lst=-1;
		print(rt);
		cout<<'\n';
	}
	return 0;
}