#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 * 1000 + 10;
const int maxn5 = 5 * 1000 * 100 + 10;
const int maxn3 = 500 + 10;
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1LL * 2 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 10;
vector<int> adj[maxn3], ans1, ans2;
long long h[maxn3][maxn3][2];
pair<pair<int, int>, int> par[maxn3][maxn3][2];
queue<pair<pair<int, int>, int>> q;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) h[i][j][0] = -1, h[i][j][1] = -1;
  h[1][n][0] = 0;
  q.push({{1, n}, 0});
  while (!q.empty()) {
    int a = q.front().first.first, b = q.front().first.second,
        t = q.front().second;
    q.pop();
    if (t == 0 and a == n and b == 1) {
      cout << h[a][b][t] / 2 << endl;
      while (a != 0 and b != 0) {
        int x = par[a][b][t].first.first, y = par[a][b][t].first.second;
        t ^= 1;
        if (t == 0)
          ans1.push_back(a);
        else
          ans2.push_back(b);
        a = x, b = y;
      }
      ans1.push_back(1);
      reverse(ans1.begin(), ans1.end());
      reverse(ans2.begin(), ans2.end());
      for (auto u : ans1) cout << u << ' ';
      cout << '\n';
      for (auto u : ans2) cout << u << ' ';
      return cout << endl, 0;
    }
    if (t == 0) {
      for (auto u : adj[a])
        if (h[u][b][1] == -1) {
          q.push({{u, b}, 1});
          h[u][b][1] = h[a][b][0] + 1;
          par[u][b][1] = {{a, b}, 0};
        }
    } else {
      for (auto u : adj[b])
        if (h[a][u][0] == -1 and u != a) {
          q.push({{a, u}, 0});
          h[a][u][0] = h[a][b][1] + 1;
          par[a][u][0] = {{a, b}, 1};
        }
    }
  }
  return cout << -1 << endl, 0;
}
