#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 * 100 + 13, MAXT = 2 + 13, MAXD = 1 * 1000 + 13;
bool mark[MAXN][MAXN][MAXT];
int dist[MAXN][MAXN][MAXT];
pair<pair<int, int>, int> par[MAXN][MAXN][MAXT];
queue<pair<pair<int, int>, int> > bfsq;
vector<int> adj[MAXN], bob, alex;
int main() {
  int n, m;
  cin >> n >> m;
  int a, b;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) dist[i][j][1] = dist[i][j][2] = MAXD;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dist[1][n][1] = 0;
  mark[1][n][1] = true;
  bfsq.push(make_pair(make_pair(1, n), 1));
  int t;
  while (!bfsq.empty()) {
    b = bfsq.front().first.first, a = bfsq.front().first.second,
    t = bfsq.front().second;
    if (t == 1) {
      for (auto i : adj[b]) {
        if (!mark[i][a][2]) {
          par[i][a][2] = bfsq.front();
          dist[i][a][2] = dist[b][a][1] + 1;
          mark[i][a][2] = true;
          bfsq.push(make_pair(make_pair(i, a), 2));
        }
      }
    } else {
      for (auto i : adj[a]) {
        if (!mark[b][i][1] and b != i) {
          par[b][i][1] = bfsq.front();
          dist[b][i][1] = dist[b][a][2] + 1;
          mark[b][i][1] = true;
          bfsq.push(make_pair(make_pair(b, i), 1));
        }
      }
    }
    bfsq.pop();
  }
  if (dist[n][1][1] > 1 * 1000) {
    cout << -1 << endl;
    return 0;
  }
  cout << dist[n][1][1] / 2 << endl;
  pair<pair<int, int>, int> tmp = {{n, 1}, 1}, begin = {{1, n}, 1};
  while (tmp != begin) {
    if (tmp.second == 1) {
      bob.push_back(tmp.first.first);
      alex.push_back(tmp.first.second);
    }
    tmp = par[tmp.first.first][tmp.first.second][tmp.second];
  }
  bob.push_back(1);
  alex.push_back(n);
  reverse(bob.begin(), bob.end());
  reverse(alex.begin(), alex.end());
  for (auto i : bob) cout << i << " ";
  cout << endl;
  for (auto i : alex) cout << i << " ";
  cout << endl;
  return 0;
}
