#代码如下

#include <iostream>
#include <set>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
vector<set<int> > map;
vector<int> visit;
vector<int> path;
stack<int> p;
queue<int> q;
int main()
{
	set<int> nu;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		map.push_back(nu);
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a].insert(b);
	}
	//深搜和广搜的路径
	for (int i = 0; i < n + 1; i++) {
		visit.push_back(0);
	}
	//深搜
	p.push(1);
	path.push_back(1);
	visit[1] = 1;
	while (!p.empty()) {
		if (!map[p.top()].empty()) {
			set<int>::iterator it = map[p.top()].begin();
			while (visit[*it] && it != map[p.top()].end()) { it++; }
			if (it != map[p.top()].end())
			{
				p.push(*it); path.push_back(*it); visit[*it] = 1;
			}
			else {
				p.pop();
			}
		}
		else {
			p.pop();
		}
	}
	for (int i = 0; i < n; i++) {
		cout << path[i] << ' ';
		visit[i + 1] = 0;//重新恢复未访问
	}
	path.clear();
	//广搜
	cout << endl;
	path.push_back(1);
	visit[1] = 1;
	q.push(1);
	while (!q.empty()) {
		if (!map[q.front()].empty()) {
			set<int>::iterator it = map[q.front()].begin();
			while (it != map[q.front()].end()) {
				if (!visit[*it]) {
					q.push(*it);
					path.push_back(*it);
					visit[*it] = 1;
				}
				it++;
			}
		}
		q.pop();
	}
	for (int i = 0; i < n; i++) {
		cout << path[i] << ' ';
	}
}