Problem: 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 

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class EFaster implements Runnable {

    private static final boolean USE_FILE_IO = false;
    private static final String FILE_IN = "e.in";
    private static final String FILE_OUT = "e.out";

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tokenizer = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(new EFaster()).start();
    }

    int n;

    class VList {
        List<Integer> list = new ArrayList<Integer>();
        int[] fixed;

        void okay() {
            fixed = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                fixed[i] = list.get(i);
            }
        }
    }

    class Triple {
        int u, v, who;

        Triple(int u, int v, int who) {
            this.u = u;
            this.v = v;
            this.who = who;
        }
    }

    VList[] e;
    int[][][] fromI, fromJ, fromK;

    private void solve() throws IOException {
        n = nextInt();

        e = new VList[n];
        for (int i = 0; i < n; i++) {
            e[i] = new VList();
        }

        int m = nextInt();

        for (int i = 0; i < m; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            e[u].list.add(v);
            e[v].list.add(u);
        }
        for (int i = 0; i < n; i++) {
            e[i].okay();
        }

        fromI = new int[n][n][2];
        fromJ = new int[n][n][2];
        fromK = new int[n][n][2];
        for (int[][] vv : fromI)
            for (int[] v : vv ) {
                Arrays.fill(v, -1);
            }

        Triple src = new Triple(0, n - 1, 0);
        Triple dst = new Triple(n - 1, 0, 0);

        LinkedList<Triple> queue = new LinkedList<Triple>();
        queue.add(src);
        fromI[src.u][src.v][src.who] = Integer.MAX_VALUE;
        fromJ[src.u][src.v][src.who] = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            if (fromI[dst.u][dst.v][dst.who] != -1) {
                break;
            }

            Triple p = queue.removeFirst();
            if (p.who == 0) {
                for (int uu : e[p.u].fixed)
                    if (fromI[uu][p.v][1] == -1) {
                        Triple next = new Triple(uu, p.v, 1);
                        queue.add(next);
                        fromI[next.u][next.v][next.who] = p.u;
                        fromJ[next.u][next.v][next.who] = p.v;
                        fromK[next.u][next.v][next.who] = p.who;
                    }
            } else {
                for (int vv : e[p.v].fixed) {

                    if (p.u == vv) {
                        continue;
                    }

                    if (fromI[p.u][vv][0] == -1) {
                        Triple next = new Triple(p.u, vv, 0);
                        queue.add(next);
                        fromI[next.u][next.v][next.who] = p.u;
                        fromJ[next.u][next.v][next.who] = p.v;
                        fromK[next.u][next.v][next.who] = p.who;
                    }
                }

            }
        }

        if (fromI[dst.u][dst.v][dst.who] != -1) {
            List<Integer> routeA = new ArrayList<Integer>();
            List<Integer> routeB = new ArrayList<Integer>();

            routeA.add(dst.u);
            routeB.add(dst.v);

            for (; ;) {
                int prevU = fromI[dst.u][dst.v][dst.who];
                int prevV = fromJ[dst.u][dst.v][dst.who];
                int prevWho = fromK[dst.u][dst.v][dst.who];

                if (prevWho == 0) {
                    routeA.add(prevU);
                } else {
                    routeB.add(prevV);
                }

                dst.u = prevU;
                dst.v = prevV;
                dst.who = prevWho;

                if (src.u == dst.u && src.v == dst.v && src.who == dst.who) {
                    break;
                }
            }

            Collections.reverse(routeA);
            Collections.reverse(routeB);

            out.println(routeA.size() - 1);

            {
                boolean first = true;
                for (int v : routeA) {
                    if (!first) {
                        out.print(' ');
                    }
                    out.print(v + 1);
                    first = false;
                }
                out.println();
            }

            {
                boolean first = true;
                for (int v : routeB) {
                    if (!first) {
                        out.print(' ');
                    }
                    out.print(v + 1);
                    first = false;
                }
                out.println();
            }

        } else {
            out.print(-1);
        }
    }

    public void run() {
        long timeStart = System.currentTimeMillis();
        try {

            if (USE_FILE_IO) {
                in = new BufferedReader(new FileReader(FILE_IN));
                out = new PrintWriter(new FileWriter(FILE_OUT));
            } else {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }

            solve();

            in.close();
            out.close();
        } catch (IOException e) {
            throw new IllegalStateException(e);
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
    }

    private String nextToken() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            tokenizer = new StringTokenizer(line);
        }
        return tokenizer.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private BigInteger nextBigInt() throws IOException {
        return new BigInteger(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

}