#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
const int N = 256;
int n, m;
vector<int>G[N];
int R[N], L[N], vis[N];
bool init[N][N];
bool pairup(int x) {
   if(vis[x]) return 0;
   vis[x] = 1;
   for(int y : G[x])
      if(L[y] == -1 || pairup(L[y])) {
         L[y] = x;
         R[x] = y;
         return 1;
      }
   return 0;
}
int main() {
   ifstream cin("strazi.in");
   ofstream cout("strazi.out");
   cin >> n >> m;
   forn(i, m) {
      int x, y;
      cin >> x >> y;
      G[x - 1].push_back(y - 1);
      init[x - 1][y - 1] = 1;
   }
   fill(R, R + n, -1);
   fill(L, L + n, -1);
   for(bool ok = 1; ok;) {
      ok = 0;
      fill(vis, vis + n, 0);
      forn(i, n) if(R[i] == -1)
         ok |= pairup(i);
   }
   int sol = 0;
   forn(i, n) if(R[i] != -1) ++sol;
   cout << n - 1 - sol << '\n';
   fill(vis, vis + n, 0);
   vector<int>path;
   forn(i, n) {
      if(!vis[i] && L[i] == -1) {
         int j = i;
         for(; j >= 0 && !vis[j]; j = R[j]) {
            vis[j] = 1;
            path.push_back(j);
         }
      }
   }

   for(int i = 0; i < (int)path.size() - 1; ++i)
      if(!init[path[i]][path[i + 1]]) cout << path[i] + 1 << ' ' << path[i + 1] + 1 << ' ';
   cout << '\n';
   for(int x : path) cout << x + 1 << ' ';
   return 0;
}