#include <bits/stdc++.h>
using namespace std;
const int N = 501;
int n, m;
vector<vector<int> > g;
pair<pair<int, int>, int> p[N][N][2];
vector<int> path1, path2;
int bfs(int a, int b) {
  queue<pair<pair<int, int>, int> > q;
  int d[N][N][2];
  memset(d, -1, sizeof(d));
  d[a][b][0] = 0;
  q.push(make_pair(make_pair(a, b), 0));
  while (!q.empty()) {
    a = q.front().first.first;
    b = q.front().first.second;
    int t = q.front().second;
    q.pop();
    if (a == n - 1 && b == 0 && t == 0) return d[a][b][t];
    if (t) {
      for (int v : g[b]) {
        if (d[a][v][0] == -1 && v != a) {
          d[a][v][0] = d[a][b][1] + 1;
          p[a][v][0] = make_pair(make_pair(a, b), 1);
          q.push(make_pair(make_pair(a, v), 0));
        }
      }
    } else {
      for (int v : g[a]) {
        if (d[v][b][1] == -1) {
          d[v][b][1] = d[a][b][0];
          p[v][b][1] = make_pair(make_pair(a, b), 0);
          q.push(make_pair(make_pair(v, b), 1));
        }
      }
    }
  }
  return -1;
}
void findPath(int a, int b, int t) {
  if (a == 0 && b == n - 1) {
    path1.push_back(1);
    path2.push_back(n);
    return;
  }
  pair<pair<int, int>, int> nx = p[a][b][t];
  findPath(nx.first.first, nx.first.second, nx.second);
  if (t == 0) {
    path1.push_back(a + 1);
    path2.push_back(b + 1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  g.resize(n);
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int res = bfs(0, n - 1);
  if (res == -1) {
    printf("-1\n");
    return 0;
  }
  printf("%d\n", res);
  findPath(n - 1, 0, 0);
  for (int i = 0; i < path1.size(); i++) printf("%d ", path1[i]);
  puts("");
  for (int i = 0; i < path2.size(); i++) printf("%d ", path2[i]);
  puts("");
  return 0;
}
