#include <bits/stdc++.h>
using namespace std;
int n, m;
int best[1000000];
vector<pair<int, int> > dp;
vector<int> e[505];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int s, t;
    scanf("%d%d", &s, &t);
    e[s].push_back(t);
    e[t].push_back(s);
  }
  memset(best, -1, sizeof(best));
  best[(((1 << 9) | n) << 1) | 0] = 0;
  dp.push_back(make_pair((((1 << 9) | n) << 1) | 0, -1));
  bool done = false;
  for (int i = 0; i < (int)dp.size() && !done; i++) {
    int status = dp[i].first;
    int s = (status >> 1) >> 9;
    int t = (status >> 1) & 0x1ff;
    if (status & 1) {
      for (int j = 0; j < (int)e[t].size() && !done; j++) {
        if (s != e[t][j]) {
          int ns = ((((s << 9) | e[t][j]) << 1) | 0);
          if (best[ns] == -1) {
            best[ns] = best[status];
            dp.push_back(make_pair(ns, dp[i].second));
            if (s == n && e[t][j] == 1) {
              done = true;
            }
          }
        }
      }
    } else {
      for (int j = 0; j < (int)e[s].size() && !done; j++) {
        int ns = ((((e[s][j] << 9) | t) << 1) | 1);
        if (best[ns] == -1) {
          best[ns] = best[status] + 1;
          dp.push_back(make_pair(ns, i));
        }
      }
    }
  }
  if (done) {
    printf("%d\n", best[dp.back().first]);
    vector<int> res;
    for (int i = (int)dp.size() - 1; i != -1; i = dp[i].second) {
      res.push_back(dp[i].first);
    }
    reverse(res.begin(), res.end());
    for (size_t i = 0; i < res.size(); i++) {
      printf("%d%c", (res[i] >> 1) >> 9, i + 1 == res.size() ? '\n' : ' ');
    }
    for (size_t i = 0; i < res.size(); i++) {
      printf("%d%c", (res[i] >> 1) & 0x1ff, i + 1 == res.size() ? '\n' : ' ');
    }
  } else {
    puts("-1");
  }
  return 0;
}
