#include <bits/stdc++.h>
struct edge_type {
  int y, next;
} edge[10010 << 1];
struct queue_type {
  int x, xx, step, fa;
} Q[250010];
int n, m, cnt, first[510], ans[510][2], head, tail;
bool bo[510][510];
void ins(int x, int y) {
  edge[++cnt].y = y;
  edge[cnt].next = first[x];
  first[x] = cnt;
}
int bfs() {
  int x, xx, k, kk, y, yy;
  Q[1].x = 1;
  Q[1].xx = n;
  bo[1][n] = true;
  for (head = tail = 1; head <= tail; head++) {
    x = Q[head].x;
    xx = Q[head].xx;
    for (k = first[x]; k; k = edge[k].next) {
      y = edge[k].y;
      for (kk = first[xx]; kk; kk = edge[kk].next) {
        yy = edge[kk].y;
        if (y != yy && !bo[y][yy]) {
          Q[++tail].x = y;
          Q[tail].xx = yy;
          Q[tail].step = Q[head].step + 1;
          Q[tail].fa = head;
          bo[y][yy] = true;
          if (y == n && yy == 1) return Q[tail].step;
        }
      }
    }
  }
  return -1;
}
int main() {
  int i, j, x, y;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    ins(x, y);
    ins(y, x);
  }
  x = bfs();
  printf("%d\n", x);
  if (x != -1) {
    head = 0;
    for (i = tail; i; i = Q[i].fa) {
      ans[++head][0] = (Q[i].x);
      ans[head][1] = Q[i].xx;
    }
    for (i = head; i > 1; i--) printf("%d ", ans[i][0]);
    printf("%d\n", ans[1][0]);
    for (i = head; i > 1; i--) printf("%d ", ans[i][1]);
    printf("%d\n", ans[1][1]);
  }
}
