#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge {
	int S,T;
}e[1000005];
struct Edgv {
	int T,Num;
};
vector <Edgv> v[1000005];
int N,M;
bool vis[100005];
int cmp_nd(Edge x,Edge y) {
	return x.T<y.T;
}
int cmp_st(Edge x,Edge y) {
	return x.S<y.S;
}
queue <int> q;
int Bfs(int sx) {
	for(int i=1;i<=N;i++) {
		vis[i]=false;
	}
	q.push(sx);
	cout<<sx<<' ';
	vis[sx]=true;
	while(q.size()>0) {
		int x=q.front();
		q.pop();
		for(unsigned int i=0;i<v[x].size();i++) {
			if(vis[v[x][i].T]==true) continue;
			cout<<v[x][i].T<<' ';
			vis[v[x][i].T]=true;
			q.push(v[x][i].T);
		}
	}
	cout<<'\n';
	return 1;
}
void Dfs(int sx) {
	cout<<sx<<' ';
	vis[sx]=true;
	for(unsigned int i=0;i<v[sx].size();i++) {
		if(vis[v[sx][i].T]==true) continue;
		Dfs(v[sx][i].T);
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>N>>M;
	for(int i=1;i<=M;i++) {
		cin>>e[i].S>>e[i].T;
	}
	sort(e+1,e+M+1,cmp_nd);
	sort(e+1,e+M+1,cmp_st);
	for(int i=1;i<=M;i++) {
		v[e[i].S].push_back((Edgv){e[i].T,i});
	}
	Dfs(1);
	cout<<'\n';
	Bfs(1);
	return 0;
}

改了一晚上了，求查错，谢谢。