#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9;
const long long maxn = 500 * 1001;
const long long mod = 998244353;
long long n, m, k;
vector<int> g[maxn], vg[maxn];
int node[510][510][2];
pair<pair<int, int>, int> nod[maxn];
queue<int> q;
bool mark[maxn];
int dis[maxn], par[maxn];
void bfs(long long u) {
  mark[u] = 1;
  dis[u] = 0;
  q.push(u);
  while (q.size()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++)
      if (mark[g[v][i]] == 0) {
        dis[g[v][i]] = dis[v] + 1;
        mark[g[v][i]] = 1;
        par[g[v][i]] = v;
        q.push(g[v][i]);
      }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    vg[u].push_back(v);
    vg[v].push_back(u);
  }
  int o = 1;
  for (int v = 1; v <= n; v++)
    for (int u = 1; u <= n; u++)
      if (u != v) {
        node[v][u][0] = o;
        nod[o] = {{v, u}, 0};
        dis[o] = INF;
        o++;
        node[v][u][1] = o;
        nod[o] = {{v, u}, 1};
        dis[o] = INF;
        o++;
      } else {
        node[v][u][1] = o;
        nod[o] = {{v, u}, 1};
        dis[o] = INF;
        o++;
      }
  for (int v = 1; v <= n; v++)
    for (int u = 1; u <= n; u++)
      if (u != v) {
        o = node[v][u][0];
        for (int ii = 0; ii < vg[v].size(); ii++)
          g[o].push_back(node[vg[v][ii]][u][1]);
        o++;
        for (int ii = 0; ii < vg[u].size(); ii++)
          if (vg[u][ii] != v) g[o].push_back(node[v][vg[u][ii]][0]);
      } else {
        for (int ii = 0; ii < vg[v].size(); ii++)
          g[node[v][v][1]].push_back(node[v][vg[v][ii]][0]);
      }
  bfs(node[1][n][0]);
  o = node[n][1][0];
  vector<int> ans, ans1;
  if (dis[o] == INF)
    cout << -1;
  else {
    cout << dis[o] / 2 << "\n";
    long long i = 0;
    while (o) {
      int v = nod[o].first.first;
      int u = nod[o].first.second;
      int t = nod[o].second;
      if (t == 1)
        ans.push_back(v);
      else
        ans1.push_back(u);
      o = par[o];
    }
    cout << 1 << " ";
    for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
    cout << "\n";
    for (int i = ans1.size() - 1; i >= 0; i--) cout << ans1[i] << " ";
  }
}
