#include <bits/stdc++.h>
using namespace std;
static const int INF = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3f;
static const double EPS = 1e-10;
static const double PI = acos(-1.0);
inline int read() {
  int X = 0;
  bool flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    X = (X << 1) + (X << 3) + ch - '0';
    ch = getchar();
  }
  if (flag) return X;
  return ~(X - 1);
}
inline void write(int X) {
  if (X < 0) {
    X = ~(X - 1);
    putchar('-');
  }
  if (X > 9) write(X / 10);
  putchar(X % 10 + '0');
}
static const int MAXN = 500 + 10;
vector<int> g[MAXN];
int d[1 << 19], pre[1 << 19];
int n, m, u, v;
int main() {
  scanf("%d%d", &n, &m);
  while (m--) {
    scanf("%d%d", &u, &v);
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  memset(d, -1, sizeof(d));
  d[n - 1] = 0;
  queue<int> Q;
  Q.push(n - 1);
  while (!Q.empty()) {
    int t = Q.front();
    Q.pop();
    bool flag = false;
    if (t & (1 << 18)) {
      flag = true;
      t ^= (1 << 18);
    }
    int u = t >> 9, v = t & 511;
    if (flag) t ^= (1 << 18);
    if (flag) {
      for (int i = 0; i < g[v].size(); i++)
        if (g[v][i] != u && d[(u << 9) | g[v][i]] == -1) {
          d[(u << 9) | g[v][i]] = d[t] + 1;
          pre[(u << 9) | g[v][i]] = t;
          Q.push((u << 9) | g[v][i]);
        }
    } else {
      for (int i = 0; i < g[u].size(); i++)
        if (d[(1 << 18) | (g[u][i] << 9) | v] == -1) {
          d[(1 << 18) | (g[u][i] << 9) | v] = d[t];
          pre[(1 << 18) | (g[u][i] << 9) | v] = t;
          Q.push((1 << 18) | (g[u][i] << 9) | v);
        }
    }
  }
  int pos = (n - 1) << 9;
  if (d[pos] == -1)
    puts("-1");
  else {
    printf("%d\n", d[pos]);
    vector<int> ans1, ans2;
    ans1.push_back(n - 1);
    ans2.push_back(0);
    while (pos != n - 1) {
      pos = pre[pre[pos]];
      ans1.push_back(pos >> 9);
      ans2.push_back(pos & 511);
    }
    reverse(ans1.begin(), ans1.end());
    reverse(ans2.begin(), ans2.end());
    for (auto it : ans1) printf("%d ", it + 1);
    puts("");
    for (auto it : ans2) printf("%d ", it + 1);
    puts("");
  }
  return 0;
}
