#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int n, m;
vector<int> edge[MAXN];
bool vis[MAXN][MAXN][2];
int pre[MAXN][MAXN][2];
int num[MAXN][MAXN][2];
struct Node {
  int x, y, z;
  Node(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
};
queue<Node> q;
int ans[MAXN][2];
int main() {
  int i, j;
  scanf("%d%d", &n, &m);
  int x, y, z;
  for (i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  memset(num, -1, sizeof(num));
  q.push(Node(1, n, 0));
  vis[1][n][0] = 1;
  num[1][n][0] = 0;
  pre[1][n][0] = -1;
  while (!q.empty()) {
    Node u = q.front();
    q.pop();
    x = u.x;
    y = u.y;
    if (x == y && u.z == 0) continue;
    if (x == n && y == 1 && u.z == 0) break;
    if (!u.z) {
      z = 1;
      for (i = 0; i < edge[x].size(); i++) {
        int v = edge[x][i];
        if (vis[v][y][z]) continue;
        vis[v][y][z] = 1;
        num[v][y][z] = num[x][y][u.z] + 1;
        pre[v][y][z] = x;
        q.push(Node(v, y, z));
      }
    } else {
      z = 0;
      for (i = 0; i < edge[y].size(); i++) {
        int v = edge[y][i];
        if (vis[x][v][z]) continue;
        vis[x][v][z] = 1;
        num[x][v][z] = num[x][y][u.z];
        pre[x][v][z] = y;
        q.push(Node(x, v, z));
      }
    }
  }
  printf("%d\n", num[n][1][0]);
  if (num[n][1][0] == -1) return 0;
  int tot1 = 0, tot2 = 0;
  x = n, y = 1, z = 0;
  while (pre[x][y][z] != -1) {
    if (z) {
      ans[tot1++][0] = x;
      x = pre[x][y][z];
    } else {
      ans[tot2++][1] = y;
      y = pre[x][y][z];
    }
    z = 1 - z;
  }
  ans[tot1++][0] = 1;
  ans[tot2++][1] = n;
  for (i = tot1 - 1; i >= 0; i--) printf("%d ", ans[i][0]);
  printf("\n");
  for (i = tot2 - 1; i >= 0; i--) printf("%d ", ans[i][1]);
  printf("\n");
  return 0;
}
