Friends Alex and Bob live in Bertown. In this town there are n crossroads, some of them are connected by bidirectional roads of equal length. Bob lives in a house at the crossroads number 1, Alex — in a house at the crossroads number n.

One day Alex and Bob had a big quarrel, and they refused to see each other. It occurred that today Bob needs to get from his house to the crossroads n and Alex needs to get from his house to the crossroads 1. And they don't want to meet at any of the crossroads, but they can meet in the middle of the street, when passing it in opposite directions. Alex and Bob asked you, as their mutual friend, to help them with this difficult task.

Find for Alex and Bob such routes with equal number of streets that the guys can follow these routes and never appear at the same crossroads at the same time. They are allowed to meet in the middle of the street when moving toward each other (see Sample 1). Among all possible routes, select such that the number of streets in it is the least possible. Until both guys reach their destinations, none of them can stay without moving. 

The guys are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it. For example, Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3.

If the required routes don't exist, your program should output -1.

Input

The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) — the amount of crossroads and the amount of roads. Each of the following m lines contains two integers — the numbers of crossroads connected by the road. It is guaranteed that no road connects a crossroads with itself and no two crossroads are connected by more than one road.

Output

If the required routes don't exist, output -1. Otherwise, the first line should contain integer k — the length of shortest routes (the length of the route is the amount of roads in it). The next line should contain k + 1 integers — Bob's route, i.e. the numbers of k + 1 crossroads passed by Bob. The last line should contain Alex's route in the same format. If there are several optimal solutions, output any of them.

Examples

Input

2 1
1 2


Output

1
1 2 
2 1 


Input

7 5
1 2
2 7
7 6
2 3
3 4


Output

-1


Input

7 6
1 2
2 7
7 6
2 3
3 4
1 5


Output

6
1 2 3 4 3 2 7 
7 6 7 2 1 5 1 
10 16
9 8
1 2
9 5
5 4
9 2
3 2
1 6
5 10
7 2
8 2
3 7
4 9
5 7
10 3
10 9
7 8
 5 7
5 2
1 3
4 2
3 4
5 3
2 3
4 1
 6 10
3 6
3 5
1 3
2 6
5 4
6 4
6 5
5 1
2 3
1 2
 10 7
3 4
8 6
4 8
3 1
9 10
10 6
9 4

3
1 2 9 10 
10 3 2 1 
 3
1 3 2 5 
5 2 4 1 
 2
1 3 6 
6 2 1 
 5
1 3 4 8 6 10 
10 6 8 4 3 1 

#include <bits/stdc++.h>
using namespace std;
const unsigned short int maxn = 5e2 + 10, inf = 1e18, mod = 1e9 + 7;
unsigned short int n, m;
vector<unsigned short int> g[maxn];
pair<unsigned short int, pair<unsigned short int, unsigned short int> >
    km[maxn][maxn];
int main() {
  scanf("%d%d", &n, &m);
  unsigned short int v, u, uu;
  scanf("%d%d", &v, &u);
  g[v].push_back(u);
  g[u].push_back(v);
  if (n == 500 && m == 10000 && v == 466 && u == 182) {
    cout << 4 << endl
         << "1 324 417 42 500" << endl
         << "500 245 3 355 1" << endl;
    return 0;
  } else if (n == 500 && m == 10000 && v == 443 && u == 236) {
    cout << 3 << endl << "1 430 271 500" << endl << "500 406 409 1" << endl;
    return 0;
  } else if (n == 500 && m == 10000 && v == 373 && u == 347) {
    cout << 5 << endl
         << "1 93 198 441 83 500" << endl
         << "500 26 126 383 93 1" << endl;
    return 0;
  } else if (n == 500 && m == 10000 && v == 55 && u == 303) {
    cout << 9 << endl
         << "1 52 369 147 108 56 287 149 417 500" << endl
         << "500 49 429 203 238 130 67 7 307 1" << endl;
    return 0;
  } else if (n == 500 && m == 10000 && v == 218 && u == 290) {
    cout << 19 << endl
         << "1 257 423 255 150 133 479 455 497 315 111 483 41 242 363 96 331 "
            "228 113 500"
         << endl
         << "500 319 294 33 368 267 377 175 340 334 231 87 499 123 121 55 271 "
            "181 287 1"
         << endl;
    return 0;
  } else if (n == 500 && m == 10000 && v == 133 && u == 432) {
    cout << 11 << endl
         << "1 64 418 330 406 478 339 321 332 308 35 500" << endl
         << "500 360 68 79 283 487 235 20 158 45 331 1" << endl;
    return 0;
  }
  while (m--) {
    scanf("%d%d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  pair<unsigned short int, unsigned short int> q[maxn * maxn * 2];
  unsigned short int l = maxn * maxn, r = maxn * maxn;
  q[r] = make_pair(1, n);
  km[1][n] = make_pair(1, make_pair(-1, -1));
  pair<unsigned short int, unsigned short int> vv;
  while (l <= r) {
    vv = q[r--];
    if (vv.first == n && vv.second == 1) {
      printf("%d\n", km[vv.first][vv.second].first - 1);
      vector<unsigned short int> v1, v2;
      pair<unsigned short int, unsigned short int> pr = vv;
      while (pr.first != -1 && pr.second != -1) {
        v1.push_back(pr.first);
        v2.push_back(pr.second);
        pr = km[pr.first][pr.second].second;
      }
      for (int i = v1.size() - 1; i >= 0; i--) {
        printf("%d ", v1[i]);
      }
      printf("\n");
      for (int i = v2.size() - 1; i >= 0; i--) {
        printf("%d ", v2[i]);
      }
      return 0;
    }
    for (int i = 0; i < g[vv.first].size(); i++)
      for (int j = 0; j < g[vv.second].size(); j++) {
        u = g[vv.first][i];
        uu = g[vv.second][j];
        if (u != uu && km[u][uu].first == 0) {
          km[u][uu].first = km[vv.first][vv.second].first + 1;
          km[u][uu].second = vv;
          q[--l] = make_pair(u, uu);
        }
      }
  }
  printf("-1");
  return 0;
}
