#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ss string
#define dd double
const int N=1e6+5;
int n,m,b[N];
vector<int>e[N];
queue<int>q;
struct E{
	int u,v;
}a[N];
bool cmp(E x,E y)
{
	if(x.u==y.u)return x.v<y.v;
	else return x.u<y.u;
}
void dfs(int x)
{
	printf("%d ",x);
	b[x]=1;
	for(int i=0;i<e[x].size();i++)
	{
		if(b[e[x][i]]==0)
		{
			b[e[x][i]]=1;
			dfs(e[x][i]);
		}
	}
}
void bfs(int xx)
{
	b[xx]=1;
	q.push(xx);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		printf("%d ",x);
		for(int i=0;i<e[x].size();i++)
		{
			if(b[e[x][i]]==0)
			{
				b[e[x][i]]=1;
				q.push(e[x][i]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].u>>a[i].v;
		a[i].u=min(a[i].u,a[i].v);
		a[i].v=max(a[i].u,a[i].v);
		e[a[i].u].push_back(a[i].v);
	}
	sort(a+1,a+m+1,cmp);
	dfs(1);
	printf("\n");
	for(int i=1;i<=n;i++)b[i]=0;
	bfs(1);
    return 0;
}

求大佬帮看错点