import java.util.*;

public class p5318 {
    static int N = 100010;
    static StringBuilder ans = new StringBuilder();
    static List<List<Integer>> q = new ArrayList<>();
    static boolean vis[] = new boolean[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        init();
        int n = in.nextInt();
        int m = in.nextInt();
        int x, y;
        while (m-- > 0) {
            x = in.nextInt();
            y = in.nextInt();
            add_edge(x, y);
        }
        sort();
        dfs(1);
        System.out.println(ans);

        Arrays.fill(vis, false);
        ans = new StringBuilder();

        bfs(1);
        System.out.println(ans);
    }

    private static void bfs(int u) {
        if (!vis[u]) {
            ans.append(u).append(" ");
            vis[u] = true;
        }
        if (!q.get(u).isEmpty()) {
            for (int x : q.get(u)) {
                if (!vis[x]) {
                    ans.append(x).append(" ");
                    vis[x] = true;
                }
            }
            for (int x : q.get(u)) {
                bfs(x);
            }
        }
    }

    private static void sort() {
        for (List<Integer> x : q) {
            Collections.sort(x);
        }
    }

    private static void dfs(int u) {
        ans.append(u).append(" ");
        vis[u] = true;
        if (!q.get(u).isEmpty()) {
            for (int x : q.get(u)) {
                if (!vis[x]) dfs(x);
            }
        }
    }

    private static void add_edge(int x, int y) {
        q.get(x).add(y);
    }

    private static void init() {
        for (int i = 1; i <= N; i++) {
            q.add(new ArrayList<>());
        }
    }
}