#include<iostream>
#include<queue>
#include<vector>
using namespace std;

vector<int>visited;

class Graph{
  public:
    Graph(int v,int a){
        vexnum = v;
        arcnum = a;
    }
    void initGraph(){
        for(int i = 1; i <= vexnum; i++){
            vex.push_back(i);
        }
        for(int i = 0; i < vexnum; i++)
        {
			vector<int> c;
			for(int j = 0; j < vexnum; j++)
        		c.push_back(0);
        	arc.push_back(c);
        	visited.push_back(0);
			}
        for(int i = 0; i < arcnum; i++)
        {
            int k, l;
            cin >> k >> l;
            arc[k-1][l-1] = 1;
        }
    }
    void DFS(int k){
   		visited[k] = 1;
   		cout << vex[k] << " ";
        for(int i = 0; i < vexnum; i++)
          if(!visited[i] && arc[k][i] == 1)
                DFS(i);
	  }
    void DFS_show(){
        initGraph();
        if(vexnum > 0)
            DFS(0);
        cout << endl;
		for(int i = 0; i < vexnum; i++)
        	visited[i] = 0;
    }
    void BFS_show(){
    	if(vexnum > 0)
    		BFS(0);
	  }
    void BFS(int k){
    	queue<int> q;
    	q.push(k); //入队顶点
    	
    	cout << vex[k] << " ";
		visited[k] = 1;
		
		while(!q.empty()) 
		{		
			k = q.front();
			q.pop();
			for(int i = 0; i < vexnum; i++)
			{
				if(!visited[i]&& arc[k][i])
				{
					cout << vex[i] << " ";
					visited[i] = 1;
					q.push(i);
				}
			}
		}
	}
  private:
    int vexnum;
    int arcnum;
    vector<vector<int> >arc;
    vector<int>vex;
};

int main(){
    int vexnum, arcnum;
    cin >> vexnum >> arcnum;
	Graph G(vexnum,arcnum);
    G.DFS_show();
    G.BFS_show();
    return 0;
}