#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
const int M = 1000000007;
const double PI = atan(1) * 4;
const int oo = 1000000000;
struct state {
  int x, y, d;
  state() {}
  state(int a, int b, int c) {
    x = a;
    y = b;
    d = c;
  }
};
int n, m, vis[501][501][2];
state P[501][501][2];
vector<vector<int> > v;
vector<int> ans1, ans2;
void solve() {
  int x = n - 1, y = 0, d = 0;
  ans1.push_back(x);
  ans2.push_back(y);
  while (x || y != n - 1 || d) {
    state &p = P[x][y][d];
    x = p.x;
    y = p.y;
    d = p.d;
    if (!d)
      ans1.push_back(x);
    else
      ans2.push_back(y);
  }
  for (int i = ans1.size() - 1; i >= 0; --i) printf("%d ", ans1[i] + 1);
  printf("\n");
  for (int i = ans2.size() - 1; i >= 0; --i) printf("%d ", ans2[i] + 1);
  printf("\n");
}
void bfs() {
  queue<state> q;
  q.push(state(0, n - 1, 0));
  vis[0][n - 1][0] = 1;
  for (int i = 0; i < n; ++i) vis[i][i][0] = 1;
  while (!q.empty()) {
    state p = q.front();
    q.pop();
    int x = p.x, y = p.y, d = p.d, cst = vis[x][y][d];
    if (x == n - 1 && !y && !d) {
      printf("%d\n", cst - 1);
      solve();
      return;
    }
    if (!d)
      for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i];
        if (vis[nx][y][1]) continue;
        vis[nx][y][1] = cst;
        P[nx][y][1] = p;
        q.push(state(nx, y, 1));
      }
    else
      for (int j = 0; j < v[y].size(); ++j) {
        int ny = v[y][j];
        if (vis[x][ny][0]) continue;
        vis[x][ny][0] = cst + 1;
        P[x][ny][0] = p;
        q.push(state(x, ny, 0));
      }
  }
  cout << -1 << endl;
}
int main() {
  cin >> n >> m;
  v.resize(n);
  for (int a, b, i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  bfs();
  return 0;
}
