#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int h[5][maxn][maxn], pr[5][maxn][maxn], n, m;
vector<int> aj[maxn];
queue<int> trn, a, b;
vector<int> ans0, ans1;
void prps(bool t, int aa, int bb) {
  if (t == 0 and aa == 0 and bb == n - 1) {
    ans1.push_back(n - 1);
    ans0.push_back(0);
    return;
  }
  if (t) {
    ans0.push_back(aa);
    prps(!t, pr[t][aa][bb], bb);
  } else {
    ans1.push_back(bb);
    prps(!t, aa, pr[t][aa][bb]);
  }
  return;
}
void psh(bool t, int aa, int bb) {
  trn.push(t);
  a.push(aa);
  b.push(bb);
}
void pp() {
  trn.pop();
  a.pop();
  b.pop();
}
void bfs() {
  h[0][0][n - 1] = 1;
  psh(0, 0, n - 1);
  while ((int)(a).size()) {
    int aa = a.front(), bb = b.front();
    bool t = trn.front();
    if (!t) {
      for (int i = 0; i < (int)(aj[aa]).size(); i++) {
        int u = aj[aa][i];
        if (!h[!t][u][bb]) {
          h[!t][u][bb] = h[t][aa][bb] + 1;
          pr[!t][u][bb] = aa;
          psh(!t, u, bb);
        }
      }
    } else {
      for (int i = 0; i < (int)(aj[bb]).size(); i++) {
        int u = aj[bb][i];
        if (!h[!t][aa][u] and u != aa) {
          h[!t][aa][u] = h[t][aa][bb] + 1;
          pr[!t][aa][u] = bb;
          psh(!t, aa, u);
        }
        if (u == 0 and aa == n - 1) return;
      }
    }
    pp();
  }
  return;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    aj[u].push_back(v);
    aj[v].push_back(u);
  }
  bfs();
  if (!h[0][n - 1][0])
    cout << -1 << endl;
  else {
    cout << h[0][n - 1][0] / 2 << endl;
    prps(0, n - 1, 0);
    for (int i = (int)(ans0).size() - 1; i >= 0; i--)
      cout << ans0[i] + 1 << ' ';
    cout << endl;
    for (int i = (int)(ans1).size() - 1; i >= 0; i--)
      cout << ans1[i] + 1 << ' ';
  }
  return false;
}
