#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int oo = numeric_limits<int>::max() / 2;
constexpr int N = 501;
int n, m;
vector<int> g[N];
int d[N][N][2];
int fromx[N][N][2];
int fromy[N][N][2];
struct State {
  State(int x_, int y_, int t_) : x(x_), y(y_), t(t_) {}
  int x, y, t;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie();
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      d[i][j][0] = d[i][j][1] = oo;
    }
  }
  fromx[0][n - 1][0] = -1;
  fromy[0][n - 1][0] = -1;
  d[0][n - 1][0] = 0;
  queue<State> q;
  q.emplace(0, n - 1, 0);
  while (!q.empty()) {
    auto& cur = q.front();
    if (cur.t == 0) {
      for (auto to : g[cur.x]) {
        if (d[to][cur.y][1] > d[cur.x][cur.y][0] + 1) {
          d[to][cur.y][1] = d[cur.x][cur.y][0] + 1;
          q.emplace(to, cur.y, 1);
          fromx[to][cur.y][1] = cur.x;
          fromy[to][cur.y][1] = cur.y;
        }
      }
    } else {
      for (auto to : g[cur.y]) {
        if (to == cur.x) {
          continue;
        }
        if (d[cur.x][to][0] > d[cur.x][cur.y][1] + 1) {
          d[cur.x][to][0] = d[cur.x][cur.y][1] + 1;
          q.emplace(cur.x, to, 0);
          fromx[cur.x][to][0] = cur.x;
          fromy[cur.x][to][0] = cur.y;
        }
      }
    }
    q.pop();
  }
  if (d[n - 1][0][0] == oo) {
    cout << -1 << endl;
  } else {
    vector<int> path[2];
    function<void(int, int, int, bool)> build = [&](int i, int j, int t,
                                                    bool flag) {
      while (1) {
        if (i == -1 || j == -1) {
          break;
        }
        int pi = fromx[i][j][t];
        int pj = fromy[i][j][t];
        if (flag) {
          path[0].push_back(i);
          path[1].push_back(j);
        } else {
          if (t == 1) {
            path[1].push_back(j);
          } else {
            path[0].push_back(i);
          }
        }
        flag = false;
        t = 1 - t;
        i = pi;
        j = pj;
      }
    };
    cout << d[n - 1][0][0] / 2 << endl;
    build(n - 1, 0, 0, true);
    reverse(path[0].begin(), path[0].end());
    for (int i : path[0]) {
      cout << (i + 1) << " ";
    }
    cout << endl;
    reverse(path[1].begin(), path[1].end());
    for (int i : path[1]) {
      cout << (i + 1) << " ";
    }
    cout << endl;
  }
  return 0;
}
