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.

Difficulty: competition

Starter code:

Solutions:
def main():
    n, m = list(map(int, input().split()))
    l = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = list(map(int, input().split()))
        l[u].append(v)
        l[v].append(u)
    res = [0] * (n + 1)
    for u, x in enumerate(res):
        if not x:
            x, nxt = -1, [u]
            while nxt:
                x, cur, nxt = -x, nxt, []
                for u in cur:
                    if l[u]:
                        res[u] = x
                        for v in l[u]:
                            if not res[v]:
                                nxt.append(v)
                            elif res[v] == x:
                                print(-1)
                                return
    for x in -1, 1:
        l = [u for u in range(1, n + 1) if res[u] == x]
        print(len(l))
        print(' '.join(map(str, l)))


def __starting_point():
    main()

__starting_point()

n, m = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

colour = [None] * n
bad = False

for i in range(n):
    if colour[i] is None:
        todo = [(i, True)]
        while todo:
            xi, xc = todo.pop()
            if colour[xi] is not None:
                if colour[xi] == xc:
                    continue
                else:
                    bad = True
                    break
            colour[xi] = xc
            for neighbour in adj[xi]:
                todo.append((neighbour, not xc))
    if bad:
        break

if bad:
    print(-1)
else:
    f = []
    t = []
    for i in range(n):
        if colour[i]:
            t.append(i+1)
        else:
            f.append(i+1)
    print(len(f))
    print(" ".join(map(str, f)))

    print(len(t))
    print(" ".join(map(str, t)))


# in the name of god

from collections import defaultdict

n, m = list(map(int, input().strip().split()))

g = defaultdict(list)

for _ in range(m):
	u, v = list(map(int, input().strip().split()))
	g[u].append(v)
	g[v].append(u)

v1 = []
v2 = []

mark = [-1] * (n + 1)

def bfs(start):
    q = []
    q.append(start)
    mark[start] = 1
    v2.append(start)

    while q:
        v = q.pop(0)

        for u in g[v]:
            if mark[u] == -1:
                mark[u] = 1 - mark[v]
                q.append(u)
                if mark[u] == 0:
                    v1.append(u)
                else:
                    v2.append(u)

            elif mark[u] == mark[v]:
                return -1
    return 0

sw = False
for i in range(1, n + 1):
    if mark[i] == -1 and len(g[i]): 
        res = bfs(i)

    try:
        if res == -1:
            sw = True
            break
    except:
        continue
if sw:
    print(-1)
else:
    print(len(v1))
    print(' '.join(str(x) for x in v1))
    print(len(v2))
    print(' '.join(str(x) for x in v2))



s = list(map(int, input().split()))
n, m = s[0], s[1]
if m == 0:
    print(-1)
    return
g = [[] for i in range(n)]

for i in range(m):
    s = list(map(int, input().split()))
    g[s[0] - 1].append(s[1] - 1)
    g[s[1] - 1].append(s[0] - 1)

vc1 = []
vc2 = []
colors = [-1 for i in range(n)]

for i in range(n):
    if colors[i] != -1:
        continue
    stack = [(i, 1)]
    colors[i] = 1
    while len(stack) > 0:
        s = stack.pop()
        if s[1] == 1:
            vc1.append(s[0] + 1)
        else:
            vc2.append(s[0] + 1)
        for j in g[s[0]]:
            if colors[j] == -1:
                stack.append((j, s[1] ^ 1))
                colors[j] = s[1] ^ 1
            elif colors[j] == s[1]:
                print(-1)
                return
print(len(vc2))
for i in vc2:
    print(i, end=' ')
print("\n", len(vc1), sep='')
for i in vc1:
    print(i, end=' ')
print()


class Graph:

    def __init__(self):
        self.numVertices = None
        self.numEdges = None
        self.neighbors = None
        self.loadGraph()

    def loadGraph(self):
        self.numVertices, self.numEdges = list(map(int, input().split()))
        self.numVertices += 1
        self.neighbors = tuple(list() for vertex in range(self.numVertices))
        self.groups = (set(), set())

        for edge in range(self.numEdges):
            vertex1, vertex2 = list(map(int, input().split()))
            self.neighbors[vertex1].append(vertex2)
            self.neighbors[vertex2].append(vertex1)

    def isBipartite(self):
        return all(self.isBipartiteComponent(vertex) for vertex in range(1, self.numVertices)
                                                              if self.groupOf(vertex) == None)
    def isBipartiteComponent(self, vertex):
        if len(self.neighbors[vertex]) == 0:
            return True

        self.groups[0].add(vertex)
        queue = [vertex]

        while queue:
            vertex = queue.pop()
            groupOfVertex = self.groupOf(vertex)

            for neighbor in self.neighbors[vertex]:
                groupOfNeighbor = self.groupOf(neighbor)

                if groupOfNeighbor == groupOfVertex:
                    return False

                elif groupOfNeighbor == None:
                    self.groups[not groupOfVertex].add(neighbor)
                    queue.append(neighbor)

        return True
    
    def groupOf(self, vertex):
        return 0 if vertex in self.groups[0] else 1 if vertex in self.groups[1] else None


def solve():
    graph = Graph()
    if graph.isBipartite():
        for group in graph.groups:
            print(len(group))
            print(" ".join(map(str, group)))
    else:
        print(-1)

def __starting_point():
    solve()

__starting_point()

def IsPossible(graph,n,color,start,isVisited):
    stack = [start]

    while stack != []:
        #print (color)
        curr = stack.pop()
        if (not isVisited[curr-1]) and (graph[curr] != []):
            isVisited[curr-1] = True
            if color[curr-1] == 0:
                color[curr-1] = 1
                for kid in graph[curr]:
                    color[kid-1] = 2
            elif color[curr-1] == 1:
                for kid in graph[curr]:
                    if color[kid-1] == 0 or color[kid-1] == 2:
                        color[kid-1] = 2
                    else:
                        return []
            else:
                for kid in graph[curr]:
                    if color[kid-1] == 0 or color[kid-1] == 1:
                        color[kid-1] = 1
                    else:
                        return []
            for kid in graph[curr]:
                stack.append(kid)

    return color

def Solve(color):
    first = []
    second = []

    for i in range(len(color)):
        if color[i] == 1:
            first.append(i+1)
        elif color[i] == 2:
            second.append(i+1)
    
    fstr = ''
    sstr = ''
    for i in first:
        fstr += str(i)+' '
    
    for i in second:
        sstr += str(i) + ' '

    print(len(first))
    print (fstr)
    print(len(second))
    print (sstr)


def main():
    n,m = list(map(int,input().split()))
    graph = {}
    for i in range(1,n+1):
        graph[i] = []
    for i in range(m):
        start,end = list(map(int,input().split()))
        graph[start].append(end)
        graph[end].append(start)

    color = [0]*n
    isVisited = [False]*n
    for i in range(n):
        color = IsPossible(graph,n,color,i+1,isVisited)
        if color == []:
            print(-1)
            return 
    Solve(color)

main()