#include <bits/stdc++.h>
using namespace std;
const long long maxn = 510, inf = 1e12;
vector<int> adj[maxn], ans[3];
pair<pair<int, int>, int> p[maxn][maxn][2];
int l[maxn][maxn][2];
bool mark[maxn][maxn][2];
queue<pair<pair<int, int>, int> > q;
void show(pair<pair<int, int>, int> pr) {
  int x = pr.first.first, y = pr.first.second, t = pr.second;
  if (x == -1 & y == -1) return;
  show(p[x][y][t]);
  if (!t) {
    ans[0].push_back(x);
    ans[1].push_back(y);
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int(i) = int(0); int(i) < int(m); ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int(i) = int(0); int(i) < int(maxn); ++i)
    for (int(j) = int(0); int(j) < int(maxn); ++j)
      p[i][j][0] = p[i][j][1] = make_pair(make_pair(-1, -1), 0);
  mark[0][n - 1][0] = true;
  q.push(make_pair(make_pair(0, n - 1), 0));
  while (!q.empty()) {
    pair<pair<int, int>, int> pr = q.front();
    q.pop();
    int x = pr.first.first, y = pr.first.second, t = pr.second;
    if (t) {
      for (int(i) = int(0); int(i) < int(adj[y].size()); ++i) {
        int next = adj[y][i];
        if (!mark[x][next][1 - t] && next != x) {
          p[x][next][1 - t] = make_pair(make_pair(x, y), t);
          l[x][next][1 - t] = l[x][y][1];
          mark[x][next][1 - t] = true;
          q.push(make_pair(make_pair(x, next), 1 - t));
        }
      }
    } else {
      for (int(i) = int(0); int(i) < int(adj[x].size()); ++i) {
        int next = adj[x][i];
        if (!mark[next][y][1 - t]) {
          p[next][y][1 - t] = make_pair(make_pair(x, y), t);
          l[next][y][1 - t] = l[x][y][0] + 1;
          mark[next][y][1 - t] = true;
          q.push(make_pair(make_pair(next, y), 1 - t));
        }
      }
    }
  }
  show(make_pair(make_pair(n - 1, 0), 0));
  if (ans[0].size() == 1)
    cout << -1 << endl;
  else {
    cout << l[n - 1][0][0] << endl;
    for (int(i) = int(0); int(i) < int(2); ++i) {
      for (int(j) = int(0); int(j) < int(ans[i].size()); ++j)
        cout << ans[i][j] + 1 << ' ';
      cout << endl;
    }
  }
  return 0;
}
