#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int maxn = 510;
int dp[maxn][maxn][2];
pair<int, int> pr[maxn][maxn][2];
vector<int> a[maxn];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int fr, to;
    scanf("%d%d", &fr, &to);
    fr--;
    to--;
    a[fr].push_back(to);
    a[to].push_back(fr);
  }
  memset(dp, -1, sizeof(dp));
  dp[0][n - 1][0] = 0;
  pr[0][n - 1][0] = make_pair(-1, -1);
  queue<pair<pair<int, int>, int>> q;
  q.push(make_pair(make_pair(0, n - 1), 0));
  while (int((q).size())) {
    int ci = q.front().first.first;
    int cj = q.front().first.second;
    int ct = q.front().second;
    q.pop();
    if (ct == 0) {
      for (int i = 0; i < int((a[ci]).size()); ++i) {
        int to = a[ci][i];
        if (dp[to][cj][1 - ct] == -1) {
          dp[to][cj][1 - ct] = dp[ci][cj][ct] + 1;
          pr[to][cj][1 - ct] = make_pair(ci, cj);
          q.push(make_pair(make_pair(to, cj), 1 - ct));
        }
      }
    } else {
      for (int i = 0; i < int((a[cj]).size()); ++i) {
        int to = a[cj][i];
        if (to != ci && dp[ci][to][1 - ct] == -1) {
          dp[ci][to][1 - ct] = dp[ci][cj][ct] + 1;
          pr[ci][to][1 - ct] = make_pair(ci, cj);
          q.push(make_pair(make_pair(ci, to), 1 - ct));
        }
      }
    }
  }
  if (dp[n - 1][0][0] == -1)
    printf("-1\n");
  else {
    printf("%d\n", dp[n - 1][0][0] / 2);
    vector<int> ans1, ans2;
    int ci = n - 1;
    int cj = 0;
    int ct = 0;
    while (ci != -1) {
      ans1.push_back(ci);
      ans2.push_back(cj);
      int ti = pr[ci][cj][ct].first;
      int tj = pr[ci][cj][ct].second;
      ci = ti;
      cj = tj;
      ct = 1 - ct;
    }
    reverse(ans1.begin(), ans1.end());
    ans1.erase(unique(ans1.begin(), ans1.end()), ans1.end());
    reverse(ans2.begin(), ans2.end());
    ans2.erase(unique(ans2.begin(), ans2.end()), ans2.end());
    for (int i = 0; i < int((ans1).size()); ++i) printf("%d ", ans1[i] + 1);
    printf("\n");
    for (int i = 0; i < int((ans2).size()); ++i) printf("%d ", ans2[i] + 1);
  }
  return 0;
}
