#include <bits/stdc++.h>
using namespace std;
mt19937 Rand(time(0));
const int maxn = 5e2 + 5;
const long long maxc = 1e9 + 7;
int n, m;
vector<int> adj[maxn];
int d[maxn][maxn];
pair<int, int> trace[maxn][maxn];
vector<int> resOne, resN;
void bfs() {
  queue<pair<int, int> > q;
  q.push(make_pair(1, n));
  memset(d, (-1), sizeof(d));
  d[1][n] = 0;
  while (!q.empty()) {
    int s = q.front().first;
    int t = q.front().second;
    q.pop();
    for (auto u : adj[s]) {
      for (auto v : adj[t]) {
        if (d[u][v] != -1 || u == v) continue;
        trace[u][v] = make_pair(s, t);
        d[u][v] = d[s][t] + 1;
        q.push(make_pair(u, v));
      }
    }
  }
  cout << d[n][1] << "\n";
  if (d[n][1] == -1) return;
  int s = 1, t = n;
  while (t != 0) {
    resOne.push_back(t);
    resN.push_back(s);
    pair<int, int> cur = trace[t][s];
    t = cur.first, s = cur.second;
  }
  reverse((resOne).begin(), (resOne).end());
  reverse((resN).begin(), (resN).end());
  for (auto u : resOne) cout << u << " ";
  cout << "\n";
  for (auto u : resN) cout << u << " ";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  bfs();
  return 0;
}
