#include <bits/stdc++.h>
int Map[502][502];
int xline[255000], yline[255000], faline[255000], l, r, next[505][505], now;
int main() {
  int n, m, a, b;
  scanf("%d%d", &n, &m);
  memset(next, 0, sizeof(next));
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a, &b);
    next[a][++next[a][0]] = b;
    next[b][++next[b][0]] = a;
  }
  l = r = 1;
  xline[l] = 1;
  yline[l] = n;
  memset(Map, -1, sizeof(Map));
  Map[1][n] = 0;
  int fina = 0;
  while (l <= r) {
    int nowx = xline[l];
    int nowy = yline[l];
    for (int i = 1; i <= next[nowx][0]; i++)
      for (int j = 1; j <= next[nowy][0]; j++) {
        int nextx = next[nowx][i];
        int nexty = next[nowy][j];
        if (Map[nextx][nexty] == -1 && nextx != nexty) {
          Map[nextx][nexty] = Map[nowx][nowy] + 1;
          r++;
          xline[r] = nextx;
          yline[r] = nexty;
          faline[r] = l;
          if (nextx == n && nexty == 1) fina = r;
        }
      }
    if (fina) break;
    l++;
  }
  printf("%d\n", Map[n][1]);
  if (Map[n][1] == -1) return 0;
  now = fina;
  while (now > 1) {
    printf("%d ", yline[now]);
    now = faline[now];
  }
  printf("%d\n", yline[now]);
  now = fina;
  while (now > 1) {
    printf("%d ", xline[now]);
    now = faline[now];
  }
  printf("%d\n", xline[now]);
  return 0;
}
