#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
int n, m, ans[MAXN][MAXN][2], parf[MAXN][MAXN][2], pars[MAXN][MAXN][2],
    to[MAXN][MAXN][2];
bool visit[MAXN][MAXN][2];
vector<int> adj[MAXN];
void bfs() {
  queue<pair<pair<int, int>, int>> q;
  visit[0][n - 1][0] = true;
  ans[0][n - 1][0] = 0;
  q.push({{0, n - 1}, 0});
  pars[0][n - 1][0] = -1;
  parf[0][n - 1][0] = -1;
  while (!q.empty()) {
    int f = q.front().first.first, sec = q.front().first.second,
        t = q.front().second;
    q.pop();
    if (t == 0) {
      for (int i = 0; i < (int)adj[f].size(); i++) {
        int u = adj[f][i];
        if (!visit[u][sec][1]) {
          visit[u][sec][1] = true;
          q.push({{u, sec}, 1});
          ans[u][sec][1] = ans[f][sec][0];
          parf[u][sec][1] = f;
          pars[u][sec][1] = sec;
          to[u][sec][1] = u;
        }
      }
    } else {
      for (int i = 0; i < (int)adj[sec].size(); i++) {
        int u = adj[sec][i];
        if (!visit[f][u][0] && f != u) {
          visit[f][u][0] = true;
          q.push({{f, u}, 0});
          ans[f][u][0] = ans[f][sec][1] + 1;
          parf[f][u][0] = f;
          pars[f][u][0] = sec;
          to[f][u][0] = u;
        }
      }
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      ans[i][j][0] = -1;
      ans[i][j][1] = -1;
    }
  bfs();
  cout << ans[n - 1][0][0] << endl;
  if (ans[n - 1][0][0] == -1) return 0;
  int vv = n - 1, uu = 0, t = 0;
  vector<int> p1, p2;
  while (parf[vv][uu][t] != -1) {
    if (t == 0)
      p2.push_back(to[vv][uu][t]);
    else
      p1.push_back(to[vv][uu][t]);
    int v2 = parf[vv][uu][t], u2 = pars[vv][uu][t];
    vv = v2, uu = u2;
    t = 1 - t;
  }
  p1.push_back(0);
  p2.push_back(n - 1);
  while (!p1.empty()) {
    cout << p1.back() + 1 << " ";
    p1.pop_back();
  }
  cout << endl;
  while (!p2.empty()) {
    cout << p2.back() + 1 << " ";
    p2.pop_back();
  }
  cout << endl;
  return 0;
}
