#include <bits/stdc++.h>
using namespace std;
const long long N = 505, inf = 1e18, mod = 1e9 + 7;
vector<long long> vec[N];
vector<long long> ans1, ans2;
queue<pair<int, pair<int, int> > > q;
long long dis[2][N][N];
pair<int, pair<int, int> > par[2][N][N];
void bfs(long long n) {
  q.push({0, {1, n}});
  dis[0][1][n] = 0;
  while (q.size()) {
    int t = q.front().first;
    int u = q.front().second.first;
    int v = q.front().second.second;
    q.pop();
    if (t == 0) {
      for (auto e : vec[u]) {
        if (dis[1][e][v] == -1) {
          dis[1][e][v] = dis[0][u][v] + 1;
          par[1][e][v] = {0, {u, v}};
          q.push({1, {e, v}});
        }
      }
    } else {
      for (auto e : vec[v]) {
        if (dis[0][u][e] == -1 && u != e) {
          dis[0][u][e] = dis[1][u][v] + 1;
          par[0][u][e] = {1, {u, v}};
          q.push({0, {u, e}});
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dis[0][i][j] = -1;
      dis[0][j][i] = -1;
      dis[1][i][j] = -1;
      dis[1][j][i] = -1;
    }
  }
  bfs(n);
  if (dis[0][n][1] == -1) return cout << -1, 0;
  cout << dis[0][n][1] / 2 << '\n';
  pair<int, pair<int, int> > x = {0, {n, 1}};
  while (x.first != 0 || x.second.first != 1 || x.second.second != n) {
    int t = x.first;
    int u = x.second.first;
    int v = x.second.second;
    ans1.push_back(u);
    ans2.push_back(v);
    x.first = par[t][u][v].first;
    x.second.first = par[t][u][v].second.first;
    x.second.second = par[t][u][v].second.second;
  }
  ans1.push_back(x.second.first);
  ans2.push_back(x.second.second);
  for (int i = 0; i < ans2.size(); i += 2) cout << ans2[i] << " ";
  cout << '\n';
  for (int i = 0; i < ans1.size(); i += 2) cout << ans1[i] << " ";
  return 0;
}
