#include<bits/stdc++.h>
using namespace std;
bool vis[100005];
vector< vector<int> > arr(100005);	
int X,Y,a,b;//X篇文章 Y个引用 

void dfs(int k){
	vis[k] = 1;
	cout << k << " ";
	for(int i = 0; i < arr[k].size(); i++){
		if(!vis[arr[k][i]]){
			dfs(arr[k][i]);
		}
	}
}

void bfs(int k){
	queue<int> q;
	q.push(k);
	cout << k << " ";
	vis[k] = 1;
	while(!q.empty()){
		int fir = q.front();
		for(int i = 0; i < arr[fir].size(); i++){
			int pos = arr[fir][i];
			if(!vis[pos]){
				q.push(pos);
				cout << pos << " ";
				vis[pos] = 1;
			}
		}
		q.pop();
	}
}
int main(){
	cin >> X >> Y;
	for(int i = 1; i <= Y; i++){
		cin >> a >> b;
		arr[a].push_back(b);
	} 
	for(int i = 1; i <= X; i++){
		sort(arr[i].begin(), arr[i].end());
	}
	for(int i = 1; i <= X; i++){
		cout << i << " : "; 
		for(int j = 0; j < arr[i].size(); j++){
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	dfs(1);
	cout << endl;
	memset(vis,false,sizeof(vis)); 
	bfs(1);
	return 0;
}