本蒟蒻刚学图。用链式前向星写的，求调! ! !

#include<bits/stdc++.h>
using namespace std;
inline int in(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void out(int x){if(x<0){putchar('-'),x=-x;}if(x>9){out(x/10);}putchar(x%10+'0');}
const int maxn=100005,maxm=1000005;
struct pooi{
	int x0,x1;
}x[maxm];
struct gra{
	int to,nxt;
}g[maxm];
int n,m,head[maxn],vis1[maxn],edgenum=0;
//建图
void addedge(int f,int t){
	g[++edgenum].nxt=head[f];
	g[edgenum].to=t;
	head[f]=edgenum;
}
bool cmp(pooi a,pooi b){
	return a.x0<=b.x0;
}
void dfs(int x){
	vis1[x]=1;
	out(x),putchar(' ');
	for(int i=head[x];i;i=g[i].nxt){
		int point=g[i].to;
		if(!vis1[point]){
			dfs(point);
		}
	}
}
void bfs(int x){
	memset(vis1,0,sizeof vis1);
	queue <int> q;
	q.push(x);
	out(x),putchar(' '); 
	vis1[x]=1; 
	while(!q.empty()){
		x=q.front();
		for(int i=head[x];i;i=g[i].nxt){
			int point=g[i].to;
			if(!vis1[point]){
				q.push(point); 
				out(point),putchar(' ');
				vis1[point]=1;
			}
		}
		q.pop();
	}
}
signed main(){
	n=in(),m=in();
	for(int i=1;i<=m;i++){
		x[i].x0=in();
		x[i].x1=in();
	}
	sort(x+1,x+m+1,cmp);
	for(int i=1;i<=m;i++){
		addedge(x[i].x0,x[i].x1);
	}
	dfs(1);
	putchar('\n');
	bfs(1);
	return 0;
}