#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<vector<int>> t(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    t[x].push_back(y);
    t[y].push_back(x);
  }
  vector<int> dist(n * n, -1);
  vector<pair<int, int>> parent(n * n, make_pair(-1, -1));
  vector<bool> order(n * n, false);
  queue<pair<int, int>> q;
  q.push(make_pair(0, n - 1));
  dist[n - 1] = 0;
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    if (p.first == n - 1 && p.second == 0) {
      int len = dist[(n - 1) * n];
      printf("%d\n", len);
      vector<int> r1, r2;
      r1.push_back(n - 1);
      r2.push_back(0);
      int pos1 = n - 1, pos2 = 0;
      while (pos1 != 0 || pos2 != n - 1) {
        int tmp = pos1;
        pos1 = parent[pos1 * n + pos2].first;
        pos2 = parent[tmp * n + pos2].second;
        r1.push_back(pos1);
        r2.push_back(pos2);
      }
      for (int i = len; i >= 0; --i) printf("%d ", r1[i] + 1);
      printf("\n");
      for (int i = len; i >= 0; --i) printf("%d ", r2[i] + 1);
      printf("\n");
      return 0;
    }
    for (auto i : t[p.first]) {
      if (order[i * n + p.second]) continue;
      order[i * n + p.second] = true;
      for (auto j : t[p.second]) {
        if (i != j && dist[i * n + j] == -1) {
          parent[i * n + j] = p;
          dist[i * n + j] = dist[p.first * n + p.second] + 1;
          q.push(make_pair(i, j));
        }
      }
    }
  }
  printf("-1\n");
  return 0;
}
