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. $u \in A$ or $v \in A$ (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 u_{i} and v_{i} (1  ≤  u_{i},  v_{i}  ≤  n), denoting an undirected edge between u_{i} and v_{i}. 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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def IsPossible(graph,n,color,start,isVisited):\n    stack = [start]\n\n    while stack != []:\n        #print (color)\n        curr = stack.pop()\n        if (not isVisited[curr-1]) and (graph[curr] != []):\n            isVisited[curr-1] = True\n            if color[curr-1] == 0:\n                color[curr-1] = 1\n                for kid in graph[curr]:\n                    color[kid-1] = 2\n            elif color[curr-1] == 1:\n                for kid in graph[curr]:\n                    if color[kid-1] == 0 or color[kid-1] == 2:\n                        color[kid-1] = 2\n                    else:\n                        return []\n            else:\n                for kid in graph[curr]:\n                    if color[kid-1] == 0 or color[kid-1] == 1:\n                        color[kid-1] = 1\n                    else:\n                        return []\n            for kid in graph[curr]:\n                stack.append(kid)\n\n    return color\n\ndef Solve(color):\n    first = []\n    second = []\n\n    for i in range(len(color)):\n        if color[i] == 1:\n            first.append(i+1)\n        elif color[i] == 2:\n            second.append(i+1)\n    \n    fstr = ''\n    sstr = ''\n    for i in first:\n        fstr += str(i)+' '\n    \n    for i in second:\n        sstr += str(i) + ' '\n\n    print(len(first))\n    print (fstr)\n    print(len(second))\n    print (sstr)\n\n\ndef main():\n    n,m = list(map(int,input().split()))\n    graph = {}\n    for i in range(1,n+1):\n        graph[i] = []\n    for i in range(m):\n        start,end = list(map(int,input().split()))\n        graph[start].append(end)\n        graph[end].append(start)\n\n    color = [0]*n\n    isVisited = [False]*n\n    for i in range(n):\n        color = IsPossible(graph,n,color,i+1,isVisited)\n        if color == []:\n            print(-1)\n            return \n    Solve(color)\n\nmain()\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14107