#include <bits/stdc++.h>
using namespace std;
struct tstate {
  int x, y, t;
  tstate() {}
  tstate(int x, int y, int t) : x(x), y(y), t(t) {}
} nxt[501][501][2];
int dist[501][501][2];
int n, m;
vector<int> g[501];
vector<int> rx, ry;
void out(int x, int y, int t) {
  if (dist[x][y][t] > 0) {
    out(nxt[x][y][t].x, nxt[x][y][t].y, nxt[x][y][t].t);
    if (t == 0) {
      ry.push_back(y);
    } else {
      rx.push_back(x);
    }
  }
}
void print() {
  out(n, 1, 0);
  cout << dist[n][1][0] / 2 << endl;
  cout << 1;
  for (int i = 0; i < rx.size(); ++i) {
    cout << " " << rx[i];
  }
  cout << endl;
  cout << n;
  for (int i = 0; i < ry.size(); ++i) {
    cout << " " << ry[i];
  }
  cout << endl;
  exit(0);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  memset(dist, -1, sizeof dist);
  dist[1][n][0] = 0;
  queue<int> q;
  q.push(1);
  q.push(n);
  q.push(0);
  for (; !q.empty();) {
    int x = q.front();
    q.pop();
    int y = q.front();
    q.pop();
    int t = q.front();
    q.pop();
    if (x == n && y == 1 && t == 0) {
      print();
    }
    if (t == 0) {
      for (int i = 0; i < g[x].size(); ++i) {
        if (dist[g[x][i]][y][1] == -1) {
          dist[g[x][i]][y][1] = dist[x][y][0] + 1;
          nxt[g[x][i]][y][1] = tstate(x, y, 0);
          q.push(g[x][i]);
          q.push(y);
          q.push(1);
        }
      }
    } else {
      for (int i = 0; i < g[y].size(); ++i) {
        if (dist[x][g[y][i]][0] == -1 && g[y][i] != x) {
          dist[x][g[y][i]][0] = dist[x][y][1] + 1;
          nxt[x][g[y][i]][0] = tstate(x, y, 1);
          q.push(x);
          q.push(g[y][i]);
          q.push(0);
        }
      }
    }
  }
  cout << -1 << endl;
}
