#include <bits/stdc++.h>
using namespace std;
const int N = 511;
int n, m;
vector<int> a[N];
bool h[N][N];
struct State {
  int x, y, last;
};
vector<State> q;
void out(int i) {
  vector<int> f1, f2;
  while (i >= 0) {
    f1.push_back(q[i].x);
    f2.push_back(q[i].y);
    i = q[i].last;
  }
  printf("%d\n", (int)f1.size() - 1);
  for (int i = 0; i < f1.size(); ++i) {
    printf("%d%s", f1[i], i == f1.size() - 1 ? "\n" : " ");
  }
  for (int i = 0; i < f2.size(); ++i) {
    printf("%d%s", f2[i], i == f2.size() - 1 ? "\n" : " ");
  }
  exit(0);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[x].push_back(y);
    a[y].push_back(x);
  }
  if (n > 1) {
    h[n][1] = true;
    q.push_back({n, 1, -1});
  }
  int op = 0;
  for (int cc = 0; cc < N; ++cc) {
    int cl = q.size();
    while (op < cl) {
      int x = q[op].x;
      int y = q[op].y;
      for (int xx : a[x])
        for (int yy : a[y])
          if (!h[xx][yy] && xx != yy) {
            h[xx][yy] = true;
            q.push_back({xx, yy, op});
            if (xx == 1 && yy == n) {
              out(q.size() - 1);
            }
          }
      ++op;
    }
  }
  puts("-1");
}
