#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int main()
{
    int n, m, x, y, v;
    queue <int> q, qq; // for finding the longest paths
    cin >> n >> m;
    int t[n][n], tt[n][n]; // t[][] changes on second route to remove all items from the first route, but tt[][] doesn't to prevent any loops
    int s[n]; // 1 if the cell doesn'z have any arrows pointing to it
    bool e[n]; // 1 if the cell doesn't have any arrows pointing from it
    for (int i = 0; i < n * n; i++) {
        t[i / n][i % n] = 0;
        tt[i / n][i % n] = 0;
    }
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        t[x - 1][y - 1] = 1;
        tt[x - 1][y - 1] = t[x - 1][y - 1]; // to back the shit up; probably  not optimal, but oh well
    }

    // fill up s[] and e[]
    for (int i = 0; i < n; i++) {
        x = 0;
        y = 0;
        for (int ii = 0; ii < n; ii++) {
            x += t[ii][i];
            y += t[i][ii];
        }
        if (x == 0) s[i] = true;
        else s[i] = false;
        if (y == 0) e[i] = true;
        else e[i] = false;
    }

    /*

    // TEMP: output all of t[][], s[] and e[]
    for (int i = 0; i < n; i++) {
        for (int ii = 0; ii < n; ii++) {
            cout << t[i][ii] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    for (int i = 0; i < n; i++) {
        cout << s[i] << " ";
    }
    cout << "\n\n";
    for (int i = 0; i < n; i++) {
        cout << e[i] << " ";
    }

    */

    // first walk
    for (int i = 0; i < n; i++) {
        if (s[i] > 0) {
            q.push(i);
            v = 1;
            while (e[q.back()] != 1) {
                x = q.back();
                for (int ii = 0; ii < n; ii++) {
                    if (t[x][ii] > 0) {
                        q.push(ii);
                        v++;
                        for (int iii = 0; iii < n; iii++) {
                            t[iii][ii] = 0; // don't worry, I still have a backup in tt[][]
                        }
                        break;
                    }
                }
            }
            break;
        }
    }

    // second walk but with avoiding the previous path as much as ever physically possible this time around
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] > 0) {
            qq.push(i);
            v++;
            while (e[qq.back()] != 1) {
                x = qq.back();
                y = 0;
                for (int ii = 0; ii < n; ii++) {
                    if (t[x][ii] > 0) {
                        qq.push(ii);
                        v++;
                        y = 1;
                        break;
                    }
                }
                if (y == 0) { // in case there is no valid path
                    for (int ii = 0; ii < n; ii++) { 
                        if (tt[x][ii] > 0) {
                            qq.push(ii);
                            y = 1;
                            break;
                        }
                    }
                }
            }
            break;
        }
    }

    // output and clear the queues, all in the dumbest way imaginable
    cout << v << "\n";
    while (!q.empty()) {
        cout << q.front() + 1 << " ";
        q.pop();
    }
    cout << 0 << "\n";
    while (!qq.empty()) {
        cout << qq.front() + 1 << " ";
        qq.pop();
    }
    cout << "0";

    return 0;
}