记录

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define cg ch=getchar()
inline int read(){
	int x=0,f=1;char cg;
	while (ch<'0'||ch>'9'){if(ch=='-')f=-1;cg;}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';cg;}
	return x*f;
}
int n,m;
vector<int>a[1000010];
bool vis[1000010];
void dfs(int x){
	vis[x]=1;
	printf("%d ",x);
	for(int i=0;i<a[x].size();i++)
		if(!vis[a[x][i]]) dfs(a[x][i]);
}
void bfs(int x){
	queue<int>q;
	q.push(x);
	while(!q.empty()){
		x=q.front();
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		printf("%d ",x);
		for(int i=0;i<a[x].size();i++)
			q.push(a[x][i]);
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u,v;
		u=read(),v=read();
		a[u].push_back(v);
	}
	for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end());
	vis[1]=1;printf("1 ");
	for(int i=0;i<a[1].size();i++) dfs(a[1][i]);
	memset(vis,0,sizeof(vis));
	printf("\n");
	bfs(1);
	return 0;
}