#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 21, inf = 1e9 + 21;
int n, m;
int h[MAXN][MAXN];
pair<int, int> par[MAXN][MAXN];
pair<int, int> tmp;
queue<pair<int, int> > q;
vector<int> adj[MAXN];
vector<int> ans, res;
inline void bfs() {
  while (!q.empty()) {
    int u = q.front().first;
    int v = q.front().second;
    q.pop();
    for (auto a : adj[u])
      for (auto b : adj[v]) {
        if (a != b && (h[a][b] > h[u][v] + 1)) {
          h[a][b] = h[u][v] + 1;
          par[a][b] = make_pair(u, v);
          q.push(make_pair(a, b));
        }
      }
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  q.push(make_pair(1, n));
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) h[i][j] = inf;
  h[1][n] = 0;
  bfs();
  if (h[n][1] == inf) return cout << -1 << '\n', 0;
  for (int i = n, j = 1; i > 0 || j > 0;) {
    tmp = par[i++][j++];
    ans.push_back(j);
    res.push_back(i);
    i = tmp.first;
    j = tmp.second;
  }
  cout << h[n][1] << '\n';
  for (int y : ans) cout << y - 1 << ' ';
  cout << '\n';
  for (int y : res) cout << y - 1 << ' ';
  return 0;
}
