Problem: Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.

Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e. <image> or <image> (or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A and B, such that both A and B are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.

Each of the next m lines contains a pair of integers ui and vi (1 ≤ ui, vi ≤ n), denoting an undirected edge between ui and vi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer k denoting the number of vertices in that vertex cover, and the second line contains k integers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.

Examples

Input

4 2
1 2
2 3


Output

1
2 
2
1 3 


Input

3 3
1 2
2 3
1 3


Output

-1

Note

In the first sample, you can give the vertex number 2 to Arya and vertices numbered 1 and 3 to Pari and keep vertex number 4 for yourself (or give it someone, if you wish).

In the second sample, there is no way to satisfy both Pari and Arya.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import java.util.NoSuchElementException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author safadurimo
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            Graph g = new Graph(n);
            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                a--;
                b--;
                g.addEdge(a, b);
            }
            BipartiteX b = new BipartiteX(g);
            if (!b.isBipartite()) {
                out.println(-1);
            } else {
                int a = 0;
                int c = 0;
                for (int i = 0; i < n; i++) {
                    if (b.color(i)) a++;
                    else c++;
                }
                out.println(a);
                for (int i = 0; i < n; i++) {
                    if (b.color(i)) out.print(i + 1 + " ");
                }
                out.println();
                out.println(c);
                for (int i = 0; i < n; i++) {
                    if (!b.color(i)) out.print(i + 1 + " ");
                }
                out.println();
            }

        }

        public class Queue<Item> implements Iterable<Item> {
            private Node<Item> first;
            private Node<Item> last;
            private int N;

            public Queue() {
                first = null;
                last = null;
                N = 0;
            }

            public boolean isEmpty() {
                return first == null;
            }

            public void enqueue(Item item) {
                Node<Item> oldlast = last;
                last = new Node<Item>();
                last.item = item;
                last.next = null;
                if (isEmpty()) first = last;
                else oldlast.next = last;
                N++;
            }

            public Item dequeue() {
                if (isEmpty()) throw new NoSuchElementException("Queue underflow");
                Item item = first.item;
                first = first.next;
                N--;
                if (isEmpty()) last = null;   // to avoid loitering
                return item;
            }

            public String toString() {
                StringBuilder s = new StringBuilder();
                for (Item item : this)
                    s.append(item + " ");
                return s.toString();
            }

            public Iterator<Item> iterator() {
                return new ListIterator<Item>(first);
            }

            private class Node<Item> {
                private Item item;
                private Node<Item> next;

            }

            private class ListIterator<Item> implements Iterator<Item> {
                private Node<Item> current;

                public ListIterator(Node<Item> first) {
                    current = first;
                }

                public boolean hasNext() {
                    return current != null;
                }

                public void remove() {
                    throw new UnsupportedOperationException();
                }

                public Item next() {
                    if (!hasNext()) throw new NoSuchElementException();
                    Item item = current.item;
                    current = current.next;
                    return item;
                }

            }

        }

        public class Bag<Item> implements Iterable<Item> {
            private Node<Item> first;
            private int N;

            public Bag() {
                first = null;
                N = 0;
            }

            public void add(Item item) {
                Node<Item> oldfirst = first;
                first = new Node<Item>();
                first.item = item;
                first.next = oldfirst;
                N++;
            }

            public Iterator<Item> iterator() {
                return new ListIterator<Item>(first);
            }

            private class Node<Item> {
                private Item item;
                private Node<Item> next;

            }

            private class ListIterator<Item> implements Iterator<Item> {
                private Node<Item> current;

                public ListIterator(Node<Item> first) {
                    current = first;
                }

                public boolean hasNext() {
                    return current != null;
                }

                public void remove() {
                    throw new UnsupportedOperationException();
                }

                public Item next() {
                    if (!hasNext()) throw new NoSuchElementException();
                    Item item = current.item;
                    current = current.next;
                    return item;
                }

            }

        }

        class Graph {
            private int V;
            private int E;
            private Bag<Integer>[] adj;

            public Graph(int V) {
                if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
                this.V = V;
                this.E = 0;
                adj = (Bag<Integer>[]) new Bag[V];
                for (int v = 0; v < V; v++) {
                    adj[v] = new Bag<Integer>();
                }
            }

            public Graph(Graph G) {
                this(G.V());
                this.E = G.E();
                for (int v = 0; v < G.V(); v++) {
                    // reverse so that adjacency list is in same order as original
                    Stack<Integer> reverse = new Stack<Integer>();
                    for (int w : G.adj[v]) {
                        reverse.push(w);
                    }
                    for (int w : reverse) {
                        adj[v].add(w);
                    }
                }
            }

            public int V() {
                return V;
            }

            public int E() {
                return E;
            }

            private void validateVertex(int v) {
                if (v < 0 || v >= V)
                    throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V - 1));
            }

            public void addEdge(int v, int w) {
                validateVertex(v);
                validateVertex(w);
                E++;
                adj[v].add(w);
                adj[w].add(v);
            }

            public Iterable<Integer> adj(int v) {
                validateVertex(v);
                return adj[v];
            }

        }

        class BipartiteX {
            private static final boolean WHITE = false;
            private boolean isBipartite;
            private boolean[] color;
            private boolean[] marked;
            private int[] edgeTo;
            private Queue<Integer> cycle;

            public BipartiteX(Graph G) {
                isBipartite = true;
                color = new boolean[G.V()];
                marked = new boolean[G.V()];
                edgeTo = new int[G.V()];

                for (int v = 0; v < G.V() && isBipartite; v++) {
                    if (!marked[v]) {
                        bfs(G, v);
                    }
                }
                assert check(G);
            }

            private void bfs(Graph G, int s) {
                Queue<Integer> q = new Queue<Integer>();
                color[s] = WHITE;
                marked[s] = true;
                q.enqueue(s);

                while (!q.isEmpty()) {
                    int v = q.dequeue();
                    for (int w : G.adj(v)) {
                        if (!marked[w]) {
                            marked[w] = true;
                            edgeTo[w] = v;
                            color[w] = !color[v];
                            q.enqueue(w);
                        } else if (color[w] == color[v]) {
                            isBipartite = false;

                            // to form odd cycle, consider s-v path and s-w path
                            // and let x be closest node to v and w common to two paths
                            // then (w-x path) + (x-v path) + (edge v-w) is an odd-length cycle
                            // Note: distTo[v] == distTo[w];
                            cycle = new Queue<Integer>();
                            Stack<Integer> stack = new Stack<Integer>();
                            int x = v, y = w;
                            while (x != y) {
                                stack.push(x);
                                cycle.enqueue(y);
                                x = edgeTo[x];
                                y = edgeTo[y];
                            }
                            stack.push(x);
                            while (!stack.isEmpty())
                                cycle.enqueue(stack.pop());
                            cycle.enqueue(w);
                            return;
                        }
                    }
                }
            }

            public boolean isBipartite() {
                return isBipartite;
            }

            public boolean color(int v) {
                if (!isBipartite)
                    throw new UnsupportedOperationException("Graph is not bipartite");
                return color[v];
            }

            public Iterable<Integer> oddCycle() {
                return cycle;
            }

            private boolean check(Graph G) {
                // graph is bipartite
                if (isBipartite) {
                    for (int v = 0; v < G.V(); v++) {
                        for (int w : G.adj(v)) {
                            if (color[v] == color[w]) {
                                System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                                return false;
                            }
                        }
                    }
                }

                // graph has an odd-length cycle
                else {
                    // verify cycle
                    int first = -1, last = -1;
                    for (int v : oddCycle()) {
                        if (first == -1) first = v;
                        last = v;
                    }
                    if (first != last) {
                        System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                        return false;
                    }
                }
                return true;
            }

        }

    }
}