#include <bits/stdc++.h>
using namespace std;
struct state {
  int bo;
  int al;
  int nMov;
  int pers;
};
vector<int> graph[502], pathAl, pathBo;
int vist[502][502][2];
int retr[502][502][2];
int n, m, BOB = 0, ALEX = 1;
void bfs() {
  memset(vist, 0, sizeof(vist));
  memset(retr, 0, sizeof(retr));
  queue<state> cola;
  state actual, next;
  actual.bo = 1;
  actual.al = n;
  actual.nMov = 0;
  actual.pers = ALEX;
  cola.push(actual);
  vist[actual.bo][actual.al][actual.pers] = 1;
  while (!cola.empty()) {
    actual = cola.front();
    cola.pop();
    if (actual.bo == n && actual.al == 1 && actual.pers == ALEX) break;
    if (actual.pers == ALEX) {
      next.pers = BOB;
      next.al = actual.al;
      next.nMov = actual.nMov + 1;
      for (int i = 0; i < graph[actual.bo].size(); i++) {
        next.bo = graph[actual.bo][i];
        if (!vist[next.bo][next.al][next.pers]) {
          vist[next.bo][next.al][next.pers] = 1;
          retr[next.bo][next.al][next.pers] = actual.bo;
          cola.push(next);
        }
      }
    } else {
      next.pers = ALEX;
      next.bo = actual.bo;
      next.nMov = actual.nMov;
      for (int i = 0; i < graph[actual.al].size(); i++) {
        next.al = graph[actual.al][i];
        if (!vist[next.bo][next.al][next.pers] && next.al != next.bo) {
          vist[next.bo][next.al][next.pers] = 1;
          retr[next.bo][next.al][next.pers] = actual.al;
          cola.push(next);
        }
      }
    }
  }
  if (actual.bo != n || actual.al != 1 || actual.pers != ALEX)
    printf("-1\n");
  else {
    for (int i = 0; i < actual.nMov * 2 + 2; i++) {
      if (actual.pers == ALEX) {
        pathAl.push_back(actual.al);
        actual.al = retr[actual.bo][actual.al][actual.pers];
        actual.pers = BOB;
      } else {
        pathBo.push_back(actual.bo);
        actual.bo = retr[actual.bo][actual.al][actual.pers];
        actual.pers = ALEX;
      }
    }
    reverse(pathAl.begin(), pathAl.end());
    reverse(pathBo.begin(), pathBo.end());
    printf("%d\n", actual.nMov);
    for (int i = 0; i < pathBo.size(); i++)
      printf("%d %c", pathBo[i], i + 1 != pathBo.size() ? ' ' : '\n');
    for (int i = 0; i < pathAl.size(); i++)
      printf("%d %c", pathAl[i], i + 1 != pathAl.size() ? ' ' : '\n');
  }
}
int main() {
  int a, b;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  bfs();
  return 0;
}
