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.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal


Solutions:
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)))


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 99999999999999999999999999999999

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		graph = [[] for i in range(n + 1)]
		col = [-1] * (n + 1)
		for i in range(m):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)
		ans = 0
		for i in range(1, n + 1):
			if col[i] == -1:
				q = deque([i])
				col[i] = 0
				while q and ans == 0:
					parent = q.pop()
					for child in graph[parent]:
						if col[child] == -1:
							col[child] = col[parent] ^ 1
							q.append(child)
						elif col[child] + col[parent] != 1:
							ans = -1
							break
			if ans == -1:
				break
		if ans == -1:
			print(ans)
		else:
			c0 = []
			c1 = []
			for i in range(1, n + 1):
				if col[i] == 0:
					c0.append(i)
				else:
					c1.append(i)
			print(len(c0))
			wia(c0)
			print(len(c1))
			wia(c1)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
edges = []
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
	edges.append((u - 1, v - 1))
col = [-1] * n
from collections import deque

def BFS(v, c):
	q = deque([(v, c)])
	while q:
		(v, c) = q.pop()
		col[v] = c
		for nv in adj[v]:
			if col[nv] == -1:
				q.append((nv, 1 - c))
for i in range(n):
	if col[i] == -1:
		BFS(i, 0)
if all((col[u] != col[v] for (u, v) in edges)):
	z = [i + 1 for i in range(n) if col[i] == 0]
	o = [i + 1 for i in range(n) if col[i] == 1]
	print(len(z))
	print(*z)
	print(len(o))
	print(*o)
else:
	print(-1)


from collections import deque
(n, m) = map(int, input().split())
e = {u: set() for u in range(n)}
for i in range(m):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	e[u].add(v)
	e[v].add(u)
c = {u: 0 for u in range(n)}
dep = set(range(n))
while len(dep) != 0:
	u = dep.pop()
	c[u] = 1
	q = deque([u])
	while len(q) != 0:
		u = q.popleft()
		for v in e[u]:
			if v not in dep:
				if c[v] == c[u]:
					print(-1)
					exit()
			else:
				dep.remove(v)
				assert c[v] == 0
				c[v] = 3 - c[u]
				q.append(v)
a = [u for u in range(n) if c[u] == 1]
b = [u for u in range(n) if c[u] == 2]
print(len(a))
print(' '.join(map(lambda x: str(x + 1), a)))
print(len(b))
print(' '.join(map(lambda x: str(x + 1), b)))


import sys, math
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math
from types import GeneratorType

def solve():

	def bootstrap(f, stack=[]):

		def wrappedfunc(*args, **kwargs):
			if stack:
				return f(*args, **kwargs)
			else:
				to = f(*args, **kwargs)
				while True:
					if type(to) is GeneratorType:
						stack.append(to)
						to = next(to)
					else:
						stack.pop()
						if not stack:
							break
						to = stack[-1].send(to)
				return to
		return wrappedfunc

	@bootstrap
	def dfs(graph, visited, node, visited_dict):
		if node not in visited:
			visited.append(node)
			visited_dict[node] = 1
		for neighbour in graph[node]:
			if neighbour not in visited_dict:
				yield dfs(graph, visited, neighbour, visited_dict)
		yield visited

	@bootstrap
	def bfs(graph, visited, node, queue, visited_dict, nodes):
		level = 1
		visited.append((node, level))
		visited_dict[node] = 1
		nodes.remove(node)
		queue.append((node, level))
		queue = col.deque(queue)
		while queue:
			(s, level) = queue.popleft()
			for neighbour in graph[s]:
				if neighbour not in visited_dict:
					visited.append((neighbour, level + 1))
					visited_dict[neighbour] = 1
					nodes.remove(neighbour)
					queue.append((neighbour, level + 1))
		yield (visited, nodes)
	(N, M) = getInts()
	graph = col.defaultdict(set)
	edges = []
	for n in range(M):
		(U, V) = getInts()
		graph[U].add(V)
		graph[V].add(U)
		edges.append((U, V))
	nodes = set([j + 1 for j in range(N)])
	connected_components = []
	(dict_A, dict_B) = (col.defaultdict(int), col.defaultdict(int))
	(A, B) = ([], [])
	while nodes:
		node = next(iter(nodes))
		(visited, nodes) = bfs(graph, [], node, [], {}, nodes)
		if len(visited) == 1:
			continue
		for (node, level) in visited:
			if level % 2 == 0:
				dict_A[node] = node
				A.append(node)
			else:
				dict_B[node] = node
				B.append(node)
	for (U, V) in edges:
		if U in dict_A and V in dict_A or (U in dict_B and V in dict_B):
			print(-1)
			return
	print(len(A))
	print(*A)
	print(len(B))
	print(*B)
	return
solve()


from collections import deque
__author__ = 'aste'

def main():
	(n, m) = [int(x) for x in input().split()]
	color = [0] * n
	graph = [[] for i in range(0, n)]
	for i in range(0, m):
		(u, v) = [int(x) - 1 for x in input().split()]
		graph[u].append(v)
		graph[v].append(u)
	res = True
	for i in range(0, n):
		if color[i] != 0:
			continue
		q = deque()
		color[i] = 1
		q.append(i)
		while q:
			v = q.popleft()
			for a in graph[v]:
				if color[a] == 0:
					color[a] = -color[v]
					q.append(a)
				elif color[a] != -color[v]:
					res = False
					break
		if not res:
			break
	if not res:
		print(-1)
	else:
		s1 = []
		s2 = []
		for i in range(0, n):
			if color[i] == 1:
				s1.append(i)
			else:
				s2.append(i)
		print(len(s1))
		print(' '.join((str(x + 1) for x in s1)))
		print(len(s2))
		print(' '.join((str(x + 1) for x in s2)))
main()


from collections import deque, defaultdict
(n, m) = map(int, input().split())
g = defaultdict(list)
visited = [-1] * (n + 1)
(x, y) = ([], [])
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	x.append(u)
	y.append(v)

def bfs(node, p):
	q = deque()
	q.append((node, p))
	while q:
		(s1, s2) = q.popleft()
		for i in g[s1]:
			if i != s2 and visited[i] == -1:
				visited[i] = 1 - visited[s1]
				q.append((i, s1))
for i in range(1, n + 1):
	if visited[i] == -1:
		visited[i] = 1
		bfs(i, -1)
for i in range(m):
	if visited[x[i]] == visited[y[i]]:
		print('-1')
		exit(0)
print(visited.count(0))
for i in range(n + 1):
	if visited[i] == 0:
		print(i, end=' ')
print()
print(visited.count(1))
for i in range(n + 1):
	if visited[i] == 1:
		print(i, end=' ')


(n, m) = map(int, input().split())
flag = False
f = [0] * 100001
E = [[] for i in range(n + 1)]
e = [tuple(map(int, input().split())) for _ in range(m)]
for (u, v) in sorted(e):
	E[u] += [v]
	E[v] += [u]

def bfs(nom, col):
	ch = [(nom, col)]
	while ch:
		(v, c) = ch.pop()
		if f[v] == 0:
			f[v] = c
			for u in E[v]:
				if f[u] == 0:
					ch += [(u, 3 - c)]
for x in range(1, n + 1):
	if f[x] == 0:
		bfs(x, 1)
for (u, v) in e:
	if f[u] == f[v]:
		flag = True
		break
if flag:
	print(-1)
else:
	a = [i for i in range(n + 1) if f[i] == 1]
	b = [i for i in range(n + 1) if f[i] == 2]
	print(len(a))
	print(*a)
	print(len(b))
	print(*b)


import sys

def make_dfs(G, **kwargs):
	col = {i: 0 for i in G}
	vis = {i: False for i in G}

	def dfs(u, color=0):
		if vis[u]:
			return
		s = set([u])
		while len(s) > 0:
			u = s.pop()
			for v in G[u]:
				if not vis[v]:
					s.add(v)
					vis[v] = True
					col[v] = 1 - col[u]
				if col[v] == col[u]:
					raise ValueError
	return (dfs, col)

def main():
	(n, m) = map(int, input().split())
	G = {i + 1: [] for i in range(n)}
	for i in range(m):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	(dfs, col) = make_dfs(G)
	try:
		for i in G:
			dfs(i)
	except ValueError:
		print(-1)
		return
	ans1 = [i for i in G if col[i] == 0]
	ans2 = [i for i in G if col[i] != 0]
	print(len(ans1))
	print(' '.join(map(str, ans1)))
	print(len(ans2))
	print(' '.join(map(str, ans2)))
main()


(n, m) = map(int, input().split())
g = [[] for _ in ' ' * n]
v = [0] * n
for _ in ' ' * m:
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
for i in range(n):
	if v[i]:
		continue
	v[i] = 1
	q = [i]
	while q:
		x = q.pop()
		for y in g[x]:
			if v[y]:
				if v[y] == v[x]:
					print(-1)
					exit(0)
			else:
				v[y] = 3 - v[x]
				q.append(y)
for i in [1, 2]:
	s = [str(k + 1) for (k, q) in enumerate(v) if q == i]
	print(len(s))
	print(' '.join(s))


f = lambda : map(int, input().split())
(n, m) = f()
s = [[] for i in range(n)]
t = [0] * n
for j in range(m):
	(x, y) = f()
	x -= 1
	y -= 1
	s[x].append(y)
	s[y].append(x)
for j in range(n):
	if t[j]:
		continue
	(p, t[j]) = ([j], 1)
	while p:
		x = p.pop()
		for y in s[x]:
			if t[y]:
				if t[y] == t[x]:
					print(-1)
					exit(0)
			else:
				t[y] = 3 - t[x]
				p.append(y)
for h in [1, 2]:
	s = [str(k) for (k, q) in enumerate(t, 1) if q == h]
	print(len(s))
	print(' '.join(s))


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()


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
edge = [list(map(int, input().split())) for i in range(m)]
edge.sort()
for (u, v) in edge:
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
s = [-1] * n

def bfs(ver, col):
	q = [(ver, col)]
	while q:
		(x, c) = q.pop()
		if s[x] == -1:
			s[x] = c
			for to in g[x]:
				if s[to] == -1:
					q.append((to, 1 - c))
for i in range(n):
	if s[i] == -1:
		bfs(i, 0)
for (u, v) in edge:
	if s[u - 1] == s[v - 1]:
		print(-1)
		break
else:
	a = [i + 1 for i in range(n) if s[i] == 0]
	b = [i + 1 for i in range(n) if s[i] == 1]
	print(len(a))
	print(*a)
	print(len(b))
	print(*b)


from collections import deque
(n, m) = map(int, input().split())
v = [[] for i in range(n + 2)]
ans = [[] for i in range(3)]
vs = [0 for i in range(n + 2)]
while m:
	(x, y) = map(int, input().split())
	v[x].append(y)
	v[y].append(x)
	m -= 1

def bfs(nod, colr):
	q = deque([nod])
	vs[nod] = 1
	while q:
		node = q.popleft()
		colr = vs[node]
		ans[colr].append(node)
		for ch in v[node]:
			if not vs[ch]:
				q.append(ch)
				vs[ch] = 3 - vs[node]
			elif vs[ch] == vs[node]:
				print(-1)
				exit()
for i in range(1, n + 1):
	if not vs[i]:
		bfs(i, 1)
print(len(ans[1]))
print(*ans[1])
print(len(ans[2]))
print(*ans[2])


inp = lambda : map(int, input().split())
(n, m) = inp()
lines = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = inp()
	lines[x].append(y)
	lines[y].append(x)
color = [-1] * (n + 1)
for j in range(1, n + 1):
	if color[j] != -1:
		continue
	head = 0
	color[j] = 0
	q = [j]
	while head < len(q):
		for i in lines[q[head]]:
			if color[i] == color[q[head]]:
				print(-1)
				quit()
			if color[i] == -1:
				q.append(i)
				color[i] = (color[q[head]] + 1) % 2
		head += 1
a = []
b = []
for i in range(len(color)):
	if color[i] == 0:
		a.append(str(i))
	if color[i] == 1:
		b.append(str(i))
print(len(a))
print(' '.join(a))
print(len(b))
print(' '.join(b))


(n, m) = map(int, input().split())
g = [set() for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
a = []
p = [-1] * n
for i in range(n):
	if p[i] != -1:
		continue
	p[i] = 0
	a.append(i)
	while a:
		x = a.pop()
		for node in g[x]:
			if p[node] == p[x]:
				print(-1)
				exit()
			if p[node] == -1:
				p[node] = not p[x]
				a.append(node)
print(p.count(0))
for i in range(n):
	if p[i] == 0:
		print(i + 1, end=' ')
print()
print(p.count(1))
for i in range(n):
	if p[i] == 1:
		print(i + 1, end=' ')
print()


from collections import defaultdict
I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
(n, m) = IL()
N = defaultdict(set)
V = [1] * (n + 1)
COL = [-1] * (n + 1)
for i in range(m):
	(a, b) = IL()
	N[a].add(b)
	N[b].add(a)
	V[a] = 0
	V[b] = 0
ans = 1
nvc = V.count(0)
vi = 0
while nvc:
	for i in range(vi, len(V)):
		if V[i] == 0:
			vi = i
			break
	V[vi] = 1
	nvc -= 1
	COL[vi] = 0
	S = {vi}
	col = 1
	while S:
		S = {v2 for v1 in S for v2 in N[v1]}
		ans *= not any((COL[s] == 1 - col for s in S))
		S = [s for s in S if not V[s]]
		for s in S:
			COL[s] = col
			V[s] = 1
			nvc -= 1
		col = 1 - col
if not ans:
	print(-1)
else:
	print(sum((c == 0 for c in COL)))
	print(*[i for (i, c) in enumerate(COL) if c == 0])
	print(sum((c == 1 for c in COL)))
	print(*[i for (i, c) in enumerate(COL) if c == 1])


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
graph = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in graph:
		graph[a] = [b]
	else:
		graph[a].append(b)
	if b not in graph:
		graph[b] = [a]
	else:
		graph[b].append(a)
seen_0 = {}
seen_1 = {}
for i in range(1, n + 1):
	if i in graph and i not in seen_0 and (i not in seen_1):
		queue = deque([i])
		seen_0[i] = 1
		while queue:
			current = queue.popleft()
			for nxt in graph[current]:
				if current in seen_0 and nxt in seen_0:
					print(-1)
					sys.exit()
				if current in seen_1 and nxt in seen_1:
					print(-1)
					sys.exit()
				if nxt not in seen_0 and nxt not in seen_1:
					if current in seen_0:
						seen_1[nxt] = 1
					else:
						seen_0[nxt] = 1
					queue.append(nxt)
print(len(seen_0))
print(*seen_0)
print(len(seen_1))
print(*seen_1)


import sys
input = sys.stdin.buffer.readline
from collections import deque

def prog():
	(n, m) = map(int, input().split())
	adj_list = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj_list[a].append(b)
		adj_list[b].append(a)
	locations = [-1 for i in range(n + 1)]
	visited = set()
	impossible = False
	for start in range(1, n + 1):
		if impossible == True:
			break
		if start in visited or len(adj_list[start]) == 0:
			continue
		s = deque([0, start])
		while len(s) > 1 and (not impossible):
			curr = s[-1]
			if curr not in visited:
				locations[curr] = (locations[s[-2]] + 1) % 2
				visited.add(curr)
			had_neighbor = False
			for i in range(len(adj_list[curr])):
				neighbor = adj_list[curr].pop()
				if neighbor not in visited:
					had_neighbor = True
					s.append(neighbor)
					break
				elif locations[curr] != (locations[neighbor] + 1) % 2:
					impossible = True
					break
			if not had_neighbor:
				s.pop()
	if impossible == True:
		print(-1)
	else:
		first_cover = []
		second_cover = []
		for i in range(1, n + 1):
			if locations[i] == 0:
				first_cover.append(str(i))
			elif locations[i] == 1:
				second_cover.append(str(i))
		print(len(first_cover))
		print(' '.join(first_cover))
		print(len(second_cover))
		print(' '.join(second_cover))
prog()


from collections import deque

def solve(adj):
	n = len(adj)
	color = [None] * n
	for u in range(n):
		if color[u] is None:
			color[u] = 0
			q = deque()
			q.append(u)
			while q:
				x = q.popleft()
				for y in adj[x]:
					if color[y] is None:
						color[y] = color[x] ^ 1
						q.append(y)
					elif color[y] == color[x]:
						return None
	return [[i for i in range(n) if color[i] == c] for c in range(2)]
(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
res = solve(adj)
if res is None:
	print(-1)
else:
	for l in res:
		print(len(l))
		print(*[e + 1 for e in l])


from collections import defaultdict
from collections import deque
(n, m) = list(map(int, input().split()))
d = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	d[x].append(y)
	d[y].append(x)
c = {}
f = 0
visited = [0] * (n + 1)
for i in range(1, n + 1):
	if visited[i] == 0:
		q = deque()
		q.append(i)
		visited[i] = 1
		while q:
			j = q.popleft()
			co = c.get(j, 0)
			if co == 0:
				c[j] = 'a'
				co = 'a'
			for k in d[j]:
				if visited[k] == 0:
					coo = c.get(k, 0)
					if coo == 0:
						c[k] = 'a' if co == 'b' else 'b'
					q.append(k)
					visited[k] = 1
for i in d:
	co = c[i]
	for j in d[i]:
		coo = c[j]
		if co == coo:
			f = 1
			break
	if f:
		break
if f:
	print(-1)
else:
	(a, b) = ([], [])
	for i in range(1, n + 1):
		co = c.get(i, 0)
		if co == 'a':
			a.append(i)
		elif co == 'b':
			b.append(i)
	print(len(a))
	print(*a)
	print(len(b))
	print(*b)


from collections import defaultdict

def dfs(g, n, visited, co, col):
	stack = []
	stack.append(n)
	while len(stack):
		s = stack[-1]
		stack.pop()
		col = col % 2 + 1
		if s not in visited:
			visited.add(s)
		for node in g[s]:
			if node in visited and co[s] == co[node]:
				print(-1)
				exit(0)
			if node not in visited:
				stack.append(node)
				if co[s] == 1:
					co[node] = 2
				elif co[s] == 2:
					co[node] = 1

def DFS(g, n):
	visited = set()
	co = {i: 0 for i in range(1, n + 1)}
	for i in range(1, n + 1):
		if i not in visited:
			co[i] = 1
			dfs(g, i, visited, co, 0)
	return co
visited = set()
(n, m) = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
co = DFS(g, n)
(o, e) = ([], [])
for k in co:
	if co[k] == 2:
		e.append(k)
	if co[k] == 1:
		o.append(k)
print(len(o))
print(*o)
print(len(e))
print(*e)


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
INF = float('inf')
mod = 10 ** 9 + 7
(n, m) = MAP()
graph = defaultdict(list)
for _ in range(m):
	(u, v) = MAP()
	graph[u].append(v)
	graph[v].append(u)
visited = [False] * (n + 1)
colorArr = [-1] * (n + 1)
for i in range(1, n + 1):
	if visited[i] == False:
		stack = [(i, 0, -1)]
		colorArr[i] = 0
		flag = 0
		while stack:
			popped = stack.pop()
			node = popped[0]
			color = popped[1]
			parent = popped[2]
			visited[node] = True
			for child in graph[node]:
				if visited[child] == False:
					stack.append((child, color ^ 1, node))
					colorArr[child] = color ^ 1
				elif child != parent:
					if colorArr[child] != color ^ 1:
						flag = 1
						break
			if flag == 1:
				break
		if flag == 1:
			break
if flag == 1:
	print(-1)
else:
	zeros = []
	ones = []
	for i in range(1, n + 1):
		if colorArr[i] == 0:
			zeros.append(i)
		else:
			ones.append(i)
	print(len(zeros))
	print(*zeros)
	print(len(ones))
	print(*ones)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def main():
	(n, m) = LI()
	aa = [LI() for _ in range(m)]
	e = collections.defaultdict(set)
	for (a, b) in aa:
		e[a].add(b)
		e[b].add(a)
	d = collections.defaultdict(lambda : None)

	def f(i, k):
		q = [(i, k)]
		while q:
			nq = []
			for (i, k) in q:
				if d[i] is not None:
					if d[i] == k:
						continue
					return False
				d[i] = k
				nk = 1 - k
				for c in e[i]:
					nq.append((c, nk))
			q = nq
		return True
	for i in range(n):
		if len(e[i]) > 0 and d[i] is None:
			r = f(i, 0)
			if not r:
				return -1
	a = []
	b = []
	for i in sorted(d.keys()):
		if d[i] is None:
			continue
		if d[i] == 1:
			a.append(i)
		else:
			b.append(i)
	return '\n'.join(map(str, [len(a), ' '.join(map(str, a)), len(b), ' '.join(map(str, b))]))
print(main())


(n, m) = map(int, input().split())
l = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	l[a].append(b)
	l[b].append(a)
v = [-1] * (n + 1)
l1 = []
l2 = []
for i in range(1, n + 1):
	if v[i] == -1:
		g = [i]
		v[i] = 1
		l1.append(i)
		while len(g) > 0:
			for x in l[g[0]]:
				if v[x] == -1:
					if v[g[0]] == 1:
						v[x] = 2
						l2.append(x)
						g.append(x)
					else:
						v[x] = 1
						l1.append(x)
						g.append(x)
				elif v[x] == v[g[0]]:
					print(-1)
					exit()
			del g[0]
print(len(l1))
print(*l1)
print(len(l2))
print(*l2)


from sys import stdin
from collections import *

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.colors) = (gdict, [], defaultdict(int))

	def find_edges(self):
		return self.edges

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_vertix(self, node):
		self.gdict[node] = []

	def add_edge(self, node1, node2):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)
		self.edges.append([node1, node2])

	def bfs(self, i):
		queue = deque([[i, 1]])
		while queue:
			(s, color) = queue.popleft()
			if self.colors[s] == 0:
				self.colors[s] = color
			for i in self.gdict[s]:
				if self.colors[i] == 0:
					queue.append([i, 3 - color])
(n, m) = map(int, input().split())
graph1 = graph()
for i in range(m):
	(u, v) = map(int, input().split())
	graph1.add_edge(u, v)
for i in range(1, n + 1):
	if graph1.colors[i] == 0:
		graph1.bfs(i)
for (i, j) in graph1.edges:
	if graph1.colors[i] == graph1.colors[j]:
		exit(print(-1))
(a, b) = ([i for i in range(n + 1) if graph1.colors[i] == 1], [i for i in range(n + 1) if graph1.colors[i] == 2])
print(len(a))
print(*a)
print(len(b))
print(*b)


(n, m) = map(int, input().split())
colors = [0] * n
edges = [[] for x in range(n)]
visited = 0
root = 0
stack = []
isPossible = True
for x in range(m):
	(i, j) = map(int, input().split())
	edges[i - 1].append(j - 1)
	edges[j - 1].append(i - 1)
while visited < n or len(stack) > 0:
	if len(stack) == 0:
		while colors[root] > 0:
			root += 1
		stack.append((root, 1))
	(current, color) = stack.pop()
	if colors[current] == color:
		continue
	elif colors[current] > 0:
		isPossible = False
		break
	visited += 1
	colors[current] = color
	color = 3 - color
	for neigh in edges[current]:
		stack.append((neigh, color))
if not isPossible:
	print(-1)
else:
	l = [[], []]
	for i in range(n):
		l[colors[i] - 1].append(i + 1)
	print(len(l[0]))
	print(*l[0])
	print(len(l[1]))
	print(*l[1])


(n, m) = map(int, input().split())
edges = {}
e = []
for i in range(m):
	(u, v) = map(int, input().split())
	e.append([u, v])
	if u in edges:
		edges[u].append(v)
	else:
		edges[u] = [v]
	if v in edges:
		edges[v].append(u)
	else:
		edges[v] = [u]
stack = [1]
visited = {1}
not_visited = set(range(2, n + 1))
l1 = {1}
l2 = set()
while not_visited:
	if not stack:
		t = not_visited.pop()
		l1.add(t)
		visited.add(t)
		stack.append(t)
	p = stack.pop()
	if p in edges:
		isL1 = p in l1
		for child in edges[p]:
			if child not in visited:
				stack.append(child)
				visited.add(child)
				not_visited.remove(child)
				if isL1:
					l2.add(child)
				else:
					l1.add(child)
for edge in e:
	(u, v) = edge
	if u not in l1 and v not in l1 or (u not in l2 and v not in l2):
		print('-1')
		break
else:
	print(len(l1))
	print(*l1)
	print(len(l2))
	print(*l2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def prime_factors(x):
	s = set()
	n = x
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			s.add(i)
		i += 1
	if n > 1:
		s.add(n)
	return s
from collections import Counter
import heapq
import math
from collections import Counter
from bisect import bisect_right
import heapq
import sys
input = sys.stdin.buffer.readline

def add(x):
	global ans
	if x >= 1 and x <= n and (arr[x] > arr[x - 1]) and (arr[x] > arr[x + 1]):
		ans += arr[x]
	elif x >= 1 and x <= n and (arr[x] < arr[x - 1]) and (arr[x] < arr[x + 1]):
		ans -= arr[x]

def erase(x):
	global ans
	if x >= 1 and x <= n and (arr[x] > arr[x - 1]) and (arr[x] > arr[x + 1]):
		ans -= arr[x]
	elif x >= 1 and x <= n and (arr[x] < arr[x - 1]) and (arr[x] < arr[x + 1]):
		ans += arr[x]
import math
from collections import deque
node = 0

def dfs(s, co):
	q = deque([s])
	c[s] = co
	vis[s] = 1
	while q:
		node = q.popleft()
		for i in g[node]:
			if vis[i] == 0:
				q.append(i)
				vis[i] = 1
				c[i] = (c[node] + 1) % 2
			elif c[i] == c[node]:
				print(-1)
				exit()
(n, m) = map(int, input().split())
g = [[] for i in range(n + 2)]
vis = [0] * (n + 2)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
c = [-1] * (n + 2)
for i in range(1, n + 1):
	if g[i] == []:
		continue
	elif vis[i] == 0:
		dfs(i, 0)
tt = []
a = []
for i in range(1, n + 1):
	if c[i] == 0:
		a.append(i)
	elif c[i] == 1:
		tt.append(i)
print(len(a))
print(*a)
print(len(tt))
print(*tt)


import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)

def main():
	global al, va, ca, ml
	(n, m) = map(int, input().split())
	ml = [-1] * (n + 1)
	al = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		al[a].append(b)
		al[b].append(a)
		ml[a] = 1
		ml[b] = 1
	va = [0] * (n + 1)
	ca = [-1] * (n + 1)
	for e in range(1, n + 1):
		if va[e] == 0:
			z = dfs(e, 0)
			if z == True:
				pass
			else:
				break
	if z == False:
		print('-1')
	else:
		print(ca.count(0))
		for i in range(1, n + 1):
			if ca[i] == 0:
				print(i, end=' ')
		print()
		print(ca.count(1))
		for i in range(1, n + 1):
			if ca[i] == 1:
				print(i, end=' ')

def dfs(n, col):
	global al, va, ca
	va[n] = 1
	ca[n] = col
	for e in al[n]:
		if va[e] == 0:
			z = dfs(e, ca[n] ^ 1)
			if z == False:
				return False
		elif ca[n] == ca[e]:
			return False
	return True
t = threading.Thread(target=main)
t.start()
t.join()


def IsPossible(graph, n, color, start, isVisited):
	stack = [start]
	while stack != []:
		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) = map(int, input().split())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(m):
		(start, end) = 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()


(n, m) = list(map(int, input().split()))
graph = [[] for _ in range(n)]
color = [0] * n
for i in range(m):
	(a, b) = list(map(int, input().split()))
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
for i in range(n):
	if color[i]:
		continue
	color[i] = 1
	queue = [i]
	while queue:
		u = queue.pop()
		for v in graph[u]:
			if color[v]:
				if color[v] == color[u]:
					print(-1)
					exit(0)
			else:
				color[v] = 3 - color[u]
				queue.append(v)
arr1 = []
arr2 = []
for i in range(len(color)):
	if color[i] == 1:
		arr1.append(i + 1)
	else:
		arr2.append(i + 1)
print(len(arr1))
print(*arr1)
print(len(arr2))
print(*arr2)


from collections import deque
lin = input().split()
(n, m) = (int(lin[0]), int(lin[1]))
graph = [[] for i in range(n)]
for i in range(m):
	curr = input().split()
	(u, v) = (int(curr[0]) - 1, int(curr[1]) - 1)
	graph[u].append(v)
	graph[v].append(u)
color = [-1 for i in range(n)]

def bipartiteBFS(source: int) -> bool:
	dq = deque()
	dq.appendleft(source)
	color[source] = 0
	colorable = True
	while len(dq) > 0 and colorable:
		curr = dq.popleft()
		for neighbor in graph[curr]:
			if color[neighbor] == -1:
				dq.append(neighbor)
				color[neighbor] = 1 - color[curr]
			elif color[neighbor] == color[curr]:
				colorable = False
	return colorable
ans = True
for node_value in range(n):
	if color[node_value] == -1:
		ans &= bipartiteBFS(node_value)
if ans:
	set1 = [index for index in range(len(color)) if color[index]]
	set2 = [index for index in range(len(color)) if not color[index]]
	print(len(set1))
	for num in set1:
		print(num + 1, end=' ')
	print()
	print(len(set2))
	for num in set2:
		print(num + 1, end=' ')
	print()
else:
	print(-1)


from collections import Counter as cntr
from math import inf

def cin():
	return map(int, input().split(' '))
(n, m) = cin()
g = {i: [] for i in range(n)}
for i in range(m):
	(u, v) = cin()
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
t = [0 for i in range(n)]
color = [-1 for i in range(n)]
flag = 0
for i in range(n):
	if t[i]:
		continue
	q = [i]
	t[i] = 1
	color[i] = 1
	while len(q) > 0:
		idx = q.pop()
		for v in g[idx]:
			if not t[v]:
				t[v] = 1
				color[v] = 3 - color[idx]
				q.append(v)
			elif color[v] == color[idx]:
				print(-1)
				exit(0)
l = cntr(color)
one = []
two = []
for v in range(n):
	if color[v] == 1:
		one.append(v + 1)
	else:
		two.append(v + 1)
print(l[1])
print(*one)
print(l[2])
print(*two)


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()


(n, m) = map(int, input().split())
G = [None] * (n + 1)
for i in range(1, n + 1):
	G[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
div = [None] * (n + 1)

def bfs():
	global n, m, G, div
	S = set((x for x in range(1, n + 1) if G[x]))
	now = []
	next = []
	while True:
		if len(now) == 0:
			if len(S) == 0:
				return True
			x = S.pop()
			now = [x]
			div[x] = 1
		for x in now:
			state = div[x]
			for v in G[x]:
				if not div[v]:
					div[v] = 3 - state
					S.remove(v)
					next.append(v)
				elif div[v] == state:
					return False
		now = next
		next = []
if not bfs():
	print('-1')
else:
	A = [str(i) for i in range(1, n + 1) if div[i] == 1]
	B = [str(i) for i in range(1, n + 1) if div[i] == 2]
	print(len(A))
	print(' '.join(A))
	print(len(B))
	print(' '.join(B))


import sys
input = sys.stdin.buffer.readline
(n, m) = list(map(int, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, v, visited, color, black, white):
		visited[v] = True
		temp = 0
		for i in self.adj[v]:
			if visited[i] == False:
				color[i] = 1 - color[v]
				if color[i] == 0:
					black.append(i + 1)
				else:
					white.append(i + 1)
				temp = (yield self.DFSUtil(i, visited, color, black, white))
				if temp == -1:
					yield (-1)
			elif color[i] == color[v]:
				yield (-1)
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)
G = Graph(n)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	G.addEdge(u - 1, v - 1)
visited = [False for _ in range(n)]
start = 0
flag = 0
color = [-1 for i in range(n)]
black = []
white = []
for i in range(0, len(visited)):
	if visited[i] == True:
		continue
	color[i] = 1
	white.append(i + 1)
	ans = G.DFSUtil(i, visited, color, black, white)
	if ans == -1:
		flag = 1
		break
if flag == 1:
	print(-1)
else:
	k = sum(color)
	print(k)
	print(*white)
	print(n - k)
	print(*black)


import sys
sys.setrecursionlimit(10 ** 6)
debug_mode = True if len(sys.argv) > 1 and sys.argv[1] == '-d' else False
if debug_mode:
	import os
	infile = open(os.path.abspath(__file__).replace('.py', '.in'))

	def input():
		return infile.readline()
from collections import defaultdict, deque

def main():
	(n_vertices, m_edges) = list(map(int, input().strip().split()))
	(G, C) = (defaultdict(list), [])
	for _ in range(m_edges):
		(u, v) = list(map(int, input().strip().split()))
		G[u].append(v)
		G[v].append(u)
	(S, X, Y) = (set(), set(), set())
	(R, B) = (0, 1)
	for u in G:
		if u in S:
			continue
		else:
			Q = deque()
			Q.append((u, R))
			while Q:
				(curr, color) = Q.popleft()
				if curr not in S:
					S.add(curr)
					if color == R:
						X.add(curr)
					else:
						Y.add(curr)
					next_color = R if color == B else B
					for v in G[curr]:
						Q.append((v, next_color))
				else:
					if curr in X and color != R:
						print(-1)
						return
					if curr in Y and color != B:
						print(-1)
						return
	XL = list(X)
	print(len(XL))
	print(' '.join((str(x) for x in XL)))
	YL = list(Y)
	print(len(YL))
	print(' '.join((str(y) for y in YL)))
main()
if debug_mode:
	infile.close()


import sys
from math import sqrt, gcd, ceil, log
from collections import defaultdict, Counter, deque
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))

def main():
	(n, m) = read()
	adj = defaultdict(list)
	for i in range(m):
		(u, v) = read()
		adj[u].append(v)
		adj[v].append(u)
	color = [0] * (n + 1)
	stk = []
	visited = [0] * (n + 1)
	col = {1: 2, 2: 1}
	for i in range(1, n + 1):
		if not visited[i] and adj[i]:
			stk = [i]
			visited[i] = 1
			color[i] = 1
			while stk:
				par = stk.pop()
				for child in adj[par]:
					if color[par] and color[par] == color[child]:
						print(-1)
						exit()
					if not visited[child]:
						color[child] = col[color[par]]
						visited[child] = 1
						stk.append(child)
	ans = [[], []]
	for i in range(1, n + 1):
		if color[i] == 1:
			ans[0].append(i)
		elif color[i] == 2:
			ans[1].append(i)
	print(len(ans[0]))
	print(*ans[0])
	print(len(ans[1]))
	print(*ans[1])
main()


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import PriorityQueue
import sys
(n, m) = map(int, stdin.readline().split())
graph = defaultdict(lambda : [])
for _ in range(m):
	(x, y) = map(int, stdin.readline().split())
	graph[x].append(y)
	graph[y].append(x)
poss = True
visited = [False] * (n + 2)
colour = [-1] * (n + 2)
for i in range(1, n + 1):
	if not visited[i] and len(graph[i]) > 0:
		visited[i] = True
		q = deque()
		q.append(i)
		colour[i] = 0
		while len(q) > 0:
			temp = q.popleft()
			for j in graph[temp]:
				if not visited[j]:
					visited[j] = True
					q.append(j)
					colour[j] = 1 - colour[temp]
				elif colour[j] == colour[temp]:
					poss = False
					break
if poss:
	one = []
	zero = []
	for i in range(len(colour)):
		if colour[i] == 0:
			zero.append(i)
		elif colour[i] == 1:
			one.append(i)
	print(len(one))
	print(*one)
	print(len(zero))
	print(*zero)
else:
	print(-1)


from sys import setrecursionlimit
setrecursionlimit(100000)
from collections import deque
UNDEF = -1
(nVertices, nEdges) = map(int, input().split())
g = [[] for _ in range(nVertices)]
edges = []
for _ in range(nEdges):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	g[u].append(v)
	g[v].append(u)
	edges.append((u, v))

def dfs(v, m):
	mark[v] = m
	for to in g[v]:
		if mark[to] == UNDEF:
			dfs(to, m ^ 1)

def bfs(v):
	q = deque([(v, 0)])
	while q:
		(v, m) = q.pop()
		mark[v] = m
		for to in g[v]:
			if mark[to] == UNDEF:
				q.appendleft((to, m ^ 1))
mark = [UNDEF] * nVertices
for v in range(nVertices):
	if mark[v] == UNDEF:
		bfs(v)
cnt1 = cnt2 = 0
for (u, v) in edges:
	cnt1 += mark[u] == 0 or mark[v] == 0
	cnt2 += mark[u] == 1 or mark[v] == 1
if cnt1 != nEdges or cnt2 != nEdges:
	print(-1)
else:
	ret = []
	ret.append('%d\n' % mark.count(0))
	vertices = []
	for v in range(nVertices):
		if mark[v] == 0:
			vertices.append(v + 1)
	ret.append('%s\n' % ' '.join(map(str, vertices)))
	ret.append('%d\n' % mark.count(1))
	vertices = []
	for v in range(nVertices):
		if mark[v] == 1:
			vertices.append(v + 1)
	ret.append('%s\n' % ' '.join(map(str, vertices)))
	print(''.join(ret))


from math import *
from collections import *
from random import *
from bisect import *
import sys
input = sys.stdin.readline
t = 1

def bfs(deg, vis, cur, par):
	qu = deque([])
	qu.append([cur, 0])
	while qu:
		x = qu.popleft()
		col[x[0]] = x[1]
		if x[1] and vis[x[0]] == 0:
			fi.append(x[0])
		elif vis[x[0]] == 0:
			se.append(x[0])
		vis[x[0]] = 1
		for i in deg[x[0]]:
			if vis[i] == 0:
				qu.append([i, 1 ^ x[1]])
				par[i] = x[0]
			elif col[x[0]] == col[i]:
				return 1
	return 0
while t:
	t -= 1
	(n, m) = map(int, input().split())
	deg = [[] for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	par = [0 for i in range(1 + n)]
	col = [0 for i in range(1 + n)]
	fi = []
	se = []
	fl = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		deg[x].append(y)
		deg[y].append(x)
	for i in range(1, n + 1):
		if vis[i] == 0:
			fl += bfs(deg, vis, i, par)
	if fl or len(fi) == 0 or len(se) == 0:
		print(-1)
	else:
		print(len(fi))
		print(*fi)
		print(len(se))
		print(*se)


from collections import defaultdict
I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
(n, m) = IL()
N = defaultdict(set)
for i in range(m):
	(a, b) = IL()
	N[a].add(b)
	N[b].add(a)
V = [0] * (n + 1)
COL = [-1] * (n + 1)
ans = 1
for i in range(1, n + 1):
	if V[i]:
		continue
	V[i] = 1
	COL[i] = 0
	S = {i}
	while S:
		v1 = S.pop()
		for v2 in N[v1]:
			if COL[v1] == COL[v2]:
				ans = 0
			elif not V[v2]:
				V[v2] = 1
				S.add(v2)
				COL[v2] = 1 - COL[v1]
if not ans:
	print(-1)
else:
	print(sum((c == 0 for c in COL)))
	print(*[i for (i, c) in enumerate(COL) if c == 0])
	print(sum((c == 1 for c in COL)))
	print(*[i for (i, c) in enumerate(COL) if c == 1])


(n, m) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = 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)))


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()


def a():
	(_, d) = (int(x) for x in input().split())
	curr_win_streak = 0
	max_win_streak = 0
	for _ in range(d):
		if '0' in input():
			curr_win_streak += 1
		else:
			curr_win_streak = 0
		max_win_streak = max(max_win_streak, curr_win_streak)
	print(max_win_streak)

def b():
	x = input()
	print(x + x[::-1])

def c():
	(nodes_nr, edges_nr) = (int(x) for x in input().split())
	node_idx___neigh_idxes = [[] for _ in range(nodes_nr + 1)]
	for _ in range(edges_nr):
		(n1, n2) = (int(x) for x in input().split())
		node_idx___neigh_idxes[n1].append(n2)
		node_idx___neigh_idxes[n2].append(n1)
	node_idx___color = [-1 for _ in range(nodes_nr + 1)]
	for node_idx in range(1, nodes_nr + 1):
		if node_idx___color[node_idx] != -1:
			continue
		stack = [node_idx]
		node_idx___color[node_idx] = 0
		while stack:
			node = stack.pop()
			curr_color = node_idx___color[node]
			neigh_color = (node_idx___color[node] + 1) % 2
			for neigh in node_idx___neigh_idxes[node]:
				if node_idx___color[neigh] == curr_color:
					print(-1)
					return
				elif node_idx___color[neigh] == -1:
					node_idx___color[neigh] = neigh_color
					stack.append(neigh)
	print(node_idx___color.count(0))
	print(*[idx for (idx, color) in enumerate(node_idx___color) if color == 0])
	print(node_idx___color.count(1))
	print(*[idx for (idx, color) in enumerate(node_idx___color) if color == 1])
c()


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(n, m) = mints()
e = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = mints()
	e[a].append(b)
	e[b].append(a)
c = [0] * (n + 1)
v = [0, 0, 0]
v[1] = []
v[2] = []
q = [0] * (n + 1)
ql = 0
qr = 0

def dfs(x):
	global qr
	d = 3 - c[x]
	for i in e[x]:
		if c[i] == 0:
			v[d].append(i)
			c[i] = d
			q[qr] = i
			qr += 1
		elif c[i] != d:
			print(-1)
			exit(0)
for i in range(1, n + 1):
	if c[i] == 0:
		c[i] = 1
		v[1].append(i)
		q[qr] = i
		qr += 1
		while ql < qr:
			dfs(q[ql])
			ql += 1
print(len(v[1]))
print(*v[1])
print(len(v[2]))
print(*v[2])


from sys import stdin
from collections import *

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.arr1, self.arr2, self.visit) = (gdict, [], defaultdict(int), defaultdict(int), defaultdict(int))

	def find_edges(self):
		return self.edges

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_vertix(self, node):
		self.gdict[node] = []

	def add_edge(self, node1, node2):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)
		self.edges.append([node1, node2])

	def bfs(self, i):
		queue = deque([[i, 1]])
		(self.visit[i], self.arr1[i]) = (1, 1)
		while queue:
			(s, level) = queue.popleft()
			for i in self.gdict[s]:
				if self.visit[i] == 0:
					queue.append([i, level + 1])
					self.visit[i] = 1
					if level % 2:
						self.arr2[i] = 1
					else:
						self.arr1[i] = 1
(n, m) = map(int, input().split())
(graph1, e1, e2) = (graph(), 0, 0)
for i in range(m):
	(u, v) = map(int, input().split())
	graph1.add_edge(u, v)
for i in range(1, n + 1):
	if not graph1.visit[i]:
		graph1.bfs(i)
(out1, out2) = (list(graph1.arr1.keys()), list(graph1.arr2.keys()))
for (i, j) in graph1.edges:
	if graph1.arr1[i] and graph1.arr2[j] or (graph1.arr1[j] and graph1.arr2[i]):
		continue
	else:
		exit(print(-1))
print(len(out1))
print(*out1)
print(len(out2))
print(*out2)


from collections import defaultdict as dd, deque as dq
(n, m) = map(int, input().split())

def bfs(a, vis, le, ri, g, lol):
	q = dq([a])
	while q:
		a = q.pop()
		vis[a] = 1
		for j in d[a]:
			if vis[j] == 0:
				if g[a] == 1:
					g[j] = 0
				else:
					g[j] = 1
				q.appendleft(j)
			elif g[a] == g[j]:
				lol[0] = 1
				return
d = dd(list)
for i in range(m):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
vis = [0] * (n + 1)
le = []
ri = []
g = [0] * (n + 1)
lol = [0]
for i in range(1, n + 1):
	if vis[i] == 0:
		bfs(i, vis, le, ri, g, lol)
if lol[0]:
	print(-1)
else:
	for i in range(1, n + 1):
		if g[i]:
			le.append(i)
		else:
			ri.append(i)
	print(len(le))
	print(*le)
	print(len(ri))
	print(*ri)


import sys
import math
import operator as op
from functools import reduce
from bisect import *
from collections import deque

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom
N = int(1000000.0) + 10
fenwick = [0] * N

def add(i, x, n):
	while i < n:
		fenwick[i] += x
		i = i | i + 1

def fsum(i, n):
	res = 0
	while i >= 0:
		res += fenwick[i]
		i = (i & i + 1) - 1
	return res

def fsum_range(i, j, n):
	return fsum(j, n) - fsum(i - 1, n)
mod = int(1000000000.0) + 7
mod2 = 998244353
t = 1
for i in range(t):
	(n, m) = read_int_line()
	adj = [-1] * (n + 1)
	for i in range(m):
		(u, v) = read_int_line()
		if adj[u] == -1:
			adj[u] = []
			adj[u].append(v)
		else:
			adj[u].append(v)
		if adj[v] == -1:
			adj[v] = []
			adj[v].append(u)
		else:
			adj[v].append(u)
	color = [-1] * (n + 1)
	f = True
	q = deque()
	for i in range(1, n + 1):
		if color[i] == -1:
			q.append(i)
			color[i] = 0
			while len(q) != 0:
				s = q.popleft()
				if adj[s] != -1:
					for i in adj[s]:
						if color[i] == -1:
							color[i] = color[s] ^ 1
							q.append(i)
						elif color[i] == color[s]:
							f = False
	if f:
		s1 = []
		s2 = []
		for i in range(1, n + 1):
			if color[i] == 1:
				s1.append(i)
			else:
				s2.append(i)
		print(len(s1))
		print(*s1)
		print(len(s2))
		print(*s2)
	else:
		print(-1)


import sys
inf = float('inf')
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
(mod, MOD) = (1000000007, 998244353)
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def is_bipartite(graph):
	n = len(graph)
	color = [-1] * n
	for start in range(n):
		if color[start] == -1:
			color[start] = 0
			stack = [start]
			while stack:
				parent = stack.pop()
				for child in graph[parent]:
					if color[child] == -1:
						color[child] = 1 - color[parent]
						stack.append(child)
					elif color[parent] == color[child]:
						return (False, color)
	return (True, color)

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, m) = get_ints()
mydict = {i: [] for i in range(n)}
for i in range(m):
	(x, y) = get_ints()
	mydict[x - 1].append(y - 1)
	mydict[y - 1].append(x - 1)
(ans, color) = is_bipartite(mydict)
if not ans:
	print(-1)
else:
	result1 = []
	result2 = []
	for i in range(n):
		if color[i] == 0:
			result1.append(i + 1)
		else:
			result2.append(i + 1)
	print(len(result1))
	print(*result1)
	print(len(result2))
	print(*result2)


(n, m) = map(int, input().split())
(eg, lay) = ([[] for _ in range(n + 1)], [0 for _ in range(n + 1)])
for (x, y) in [map(int, input().split()) for _ in range(m)]:
	(eg[x].append(y), eg[y].append(x))

def dfs(now, lab):
	(q, lay[now]) = ([now], 1)
	while q:
		fa = q.pop()
		lab = lay[fa]
		for i in eg[fa]:
			if lab * lay[i] == 1:
				return 1
			elif not lay[i]:
				lay[i] = -lab
				q.append(i)
	return 0
ok = 1
for i in range(1, n + 1):
	if lay[i] == 0:
		if dfs(i, 1):
			ok = 0
if not ok:
	print(-1)
else:
	nn = [i for i in range(1, n + 1) if lay[i] == 1]
	pn = [i for i in range(1, n + 1) if lay[i] == -1]
	print(len(nn))
	print(' '.join(map(str, nn)))
	print(len(pn))
	print(' '.join(map(str, pn)))


def dfs(v, c, a, u, col):
	q = []
	q.append(v)
	col[v] = c
	u[v] = True
	bad = 0
	r = 0
	while r < len(q):
		v = q[r]
		r += 1
		for to in a[v]:
			if u[to] and col[to] == col[v]:
				bad = 1
			elif not u[to]:
				q.append(to)
				col[to] = 1 - col[v]
				u[to] = True
	return bad
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append([])
u = [False] * n
col = [0] * n
bad = 0
for i in range(m):
	(x, y) = map(int, input().split())
	a[x - 1].append(y - 1)
	a[y - 1].append(x - 1)
for i in range(n):
	if not u[i]:
		bad += dfs(i, 0, a, u, col)
if bad > 0:
	print(-1)
else:
	print(sum(col))
	for i in range(n):
		if col[i] == 1:
			print(i + 1)
	print(n - sum(col))
	for i in range(n):
		if col[i] == 0:
			print(i + 1)


(n, m) = map(int, input().split())
(x, y) = ([], [])
res = [-1] * (n + 1)
adj = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
	x.append(u)
	y.append(v)

def dfs(u, p):
	stk = [(u, p)]
	while stk:
		(u, p) = stk[-1]
		stk.pop()
		for v in adj[u]:
			if v != p and res[v] == -1:
				res[v] = 1 - res[u]
				stk.append((v, u))
for i in range(1, n + 1):
	if res[i] == -1:
		res[i] = 1
		dfs(i, -1)
for i in range(m):
	if res[x[i]] == res[y[i]]:
		print(-1)
		exit()
print(res.count(0))
print(*[i for i in range(n + 1) if res[i] == 0])
print(res.count(1))
print(*[i for i in range(n + 1) if res[i] == 1])


def abhi(node):
	visited[node] = 1
	color[node] = 1
	q = [node]
	while q:
		a = q.pop(0)
		for j in adj[a]:
			if visited[j] == 0:
				if color[a] == 1:
					color[j] = 2
				elif color[a] == 2:
					color[j] = 1
				q.append(j)
				visited[j] = 1
			elif color[j] == color[a]:
				print(-1)
				exit(0)
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
adj = [[] for j in range(n + 1)]
for i in range(q):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
visited = [0] * (n + 1)
color = [0] * (n + 1)
for j in range(1, n + 1):
	if visited[j] == 0:
		abhi(j)
	else:
		continue
one = []
two = []
u = True
if u == True:
	for j in range(n + 1):
		if visited[j] == 1:
			if color[j] == 1:
				one.append(j)
			elif color[j] == 2:
				two.append(j)
	print(len(one))
	print(*one)
	print(len(two))
	print(*two)
else:
	print(-1)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def dfs(i):
	q = deque()
	q.append((i, 0))
	while q:
		x = q.popleft()
		if color[x[0]] == -1:
			color[x[0]] = x[1]
		elif color[x[0]] != x[1]:
			return True
		c = abs(x[1] - 1)
		v[x[0]] = True
		for f in g[x[0]]:
			if not v[f]:
				q.append((f, c))
	return False
(n, k) = map(int, input().split(' '))
g = [list() for i in range(n + 1)]
v = [0] * (n + 1)
color = [-1] * (n + 1)
for i in range(k):
	(x, y) = map(int, input().split(' '))
	g[x].append(y)
	g[y].append(x)
for i in range(1, n + 1):
	if not v[i]:
		a = dfs(i)
		if a:
			break
if a:
	print(-1)
else:
	a1 = []
	a2 = []
	for i in range(1, n + 1):
		if color[i]:
			a1.append(i)
		else:
			a2.append(i)
	print(len(a1))
	print(*a1)
	print(len(a2))
	print(*a2)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
G = defaultdict(list)

def addEdge(a, b):
	G[a].append(b)
	G[b].append(a)
(N, M) = aj()
vis = [False] * (N + 1)
col = [-1] * (N + 1)

def dfs(node):
	s = deque()
	vis[node] = True
	col[node] = 0
	c = 0
	s.append((node, c))
	while s:
		(x, y) = s.pop()
		for i in G.get(x, []):
			if not vis[i]:
				vis[i] = True
				s.append((i, y ^ 1))
				col[i] = y ^ 1
			elif y == col[i]:
				print(-1)
				exit(0)
node = 1
edge = []
for i in range(M):
	(u, v) = aj()
	edge.append((u, v))
	addEdge(u, v)
	node = u
for (i, j) in edge:
	if not vis[i]:
		dfs(i)
	if not vis[j]:
		dfs(j)
A = set()
B = set()
for (i, j) in edge:
	if col[i] == col[j]:
		print(-1)
		exit(0)
	if col[i]:
		A.add(i)
		B.add(j)
	else:
		B.add(i)
		A.add(j)
print(len(A))
print(*A)
print(len(B))
print(*B)


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	d = dict()
	arra = set()
	arrb = set()
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a not in d:
			d[a] = []
		if b not in d:
			d[b] = []
		d[a].append(b)
		d[b].append(a)
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i]:
			continue
		if i not in d:
			continue
		stack = [(i, 0)]
		while stack:
			(x, y) = stack.pop()
			if vis[x]:
				continue
			vis[x] = 1
			if y:
				arra.add(x)
			else:
				arrb.add(x)
			for item in d[x]:
				if vis[item] == 0:
					stack.append((item, 1 - y))
				elif item in arra:
					if y == 1:
						print(-1)
						exit()
				elif y == 0:
					print(-1)
					exit()
	print(len(arra))
	print(*arra)
	print(len(arrb))
	print(*arrb)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m) = [int(x) for x in input().split()]
G = []
for i in range(n):
	G.append([])
for i in range(m):
	(x, y) = [int(x) - 1 for x in input().split()]
	G[y].append(x)
	G[x].append(y)
Checked = [0] * n
new = 0
A = [[0]]
DA = {0: 0}
B = [G[0][:]]
DB = {}
for i in G[0]:
	DB[i] = 0
	Checked[i] = 1
Checked[0] = 1
aused = 0
alastchecked = 0
bused = len(G[0]) - 1
blastchecked = -1
while len(DA) + len(DB) < n:
	if alastchecked < aused:
		alastchecked += 1
		for v in G[A[-1][alastchecked]]:
			if not v in DB:
				B[-1].append(v)
				DB[v] = 0
				Checked[v] = 1
				bused += 1
	elif blastchecked < bused:
		blastchecked += 1
		for v in G[B[-1][blastchecked]]:
			if not v in DA:
				A[-1].append(v)
				DA[v] = 0
				Checked[v] = 1
				aused += 1
	else:
		B.append([])
		while Checked[new] == 1:
			new += 1
		A.append([new])
		DA[new] = 0
		aused = 0
		Checked[new] = 1
		alastchecked = -1
		bused = -1
		blastchecked = -1
bad = False
for i in range(len(A)):
	aused = len(A[-i]) - 1
	alastchecked = -1
	bused = len(B[-i]) - 1
	blastchecked = -1
	while alastchecked + blastchecked < len(A[-i]) + len(B[-i]) - 2:
		if alastchecked < aused:
			alastchecked += 1
			for v in G[A[-i][alastchecked]]:
				if not v in DB:
					bad = True
				if v in DA:
					bad = True
		if blastchecked < bused:
			blastchecked += 1
			for v in G[B[-i][blastchecked]]:
				if not v in DA:
					bad = True
				if v in DB:
					bad = True
if not bad:
	print(len(DA))
	for i in A:
		for j in i:
			print(j + 1, end=' ')
	print('\n' + str(len(DB)))
	for i in B:
		for j in i:
			print(j + 1, end=' ')
else:
	print(-1)


from collections import deque
(n, m) = list(map(int, input().split()))
g = [[] for i in range(n)]
a = []
for i in range(m):
	a.append(list(map(int, input().split())))
for i in a:
	g[i[0] - 1].append(i[1] - 1)
	g[i[1] - 1].append(i[0] - 1)
dola1 = set()
dola2 = set()
used = [0] * n
for i in range(n):
	if not used[i]:
		used[i] = 1
		q = deque()
		q.append(i)
		dola1.add(i)
		k = 0
		while q:
			v = q.popleft()
			for j in g[v]:
				if not used[j]:
					used[j] = 1
					q.append(j)
					if v in dola1:
						dola2.add(j)
					else:
						dola1.add(j)
				elif v in dola1:
					if j in dola1:
						print(-1)
						exit()
				elif j in dola2:
					print(-1)
					exit()
				k += 1
print(len(dola1))
for i in dola1:
	print(i + 1, end=' ')
print()
print(len(dola2))
for i in dola2:
	print(i + 1, end=' ')


import sys

def solve():
	(n, m) = [int(x) for x in input().split()]
	E = {i: [] for i in range(n)}
	for i in range(m):
		(u, v) = [int(x) - 1 for x in input().split()]
		E[u].append(v)
		E[v].append(u)
	color = [None] * n
	stack = []
	for v in range(n):
		if color[v] is None:
			stack.append((v, True))
			while stack:
				(u, col) = stack.pop()
				color[u] = col
				for w in E[u]:
					if color[w] is None:
						stack.append((w, not col))
					elif color[w] == col:
						print(-1)
						return None
	A = list(filter(lambda v: color[v - 1], range(1, n + 1)))
	B = list(filter(lambda v: not color[v - 1], range(1, n + 1)))
	if n == 1:
		print(-1)
	elif m == 0:
		print(1)
		print(1)
		print(n - 1)
		print(' '.join(map(str, range(2, n + 1))))
	else:
		print(len(A))
		print(' '.join(map(str, A)))
		print(len(B))
		print(' '.join(map(str, B)))
solve()


from sys import stdin, stdout

class SOLVE:

	def bfs(self, src, node, color, A, B):
		color[src] = 0
		queue = [src]
		while len(queue):
			u = queue[0]
			del queue[0]
			(A if color[u] else B).append(str(u))
			for v in node[u]:
				if color[v] == None:
					color[v] = color[u] ^ 1
					queue.append(v)
				elif color[v] == color[u]:
					return 0
		return 1

	def solve(self):
		R = stdin.readline
		W = stdout.write
		(n, m) = [int(x) for x in R().split()]
		node = [[] for i in range(n + 1)]
		for i in range(m):
			(u, v) = [int(x) for x in R().split()]
			node[u].append(v)
			node[v].append(u)
		A = []
		B = []
		color = [None for i in range(n + 1)]
		for i in range(1, n + 1):
			if len(node[i]) and color[i] == None:
				ret = self.bfs(i, node, color, A, B)
				if not ret:
					W('-1\n')
					return 0
		W('%d\n' % len(A))
		W(' '.join(A) + '\n')
		W('%d\n' % len(B))
		W(' '.join(B) + '\n')
		return 0

def main():
	s = SOLVE()
	s.solve()
main()


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(n, m) = Neo()
G = defaultdict(list)
for i in range(m):
	(a, b) = Neo()
	G[a] += [b]
	G[b] += [a]
vis = [0] * (n + 1)
f = 0

def hello(node):
	global f, A, B
	st = deque([(node, 'a')])
	while st:
		(t, color) = st.pop()
		p = ''
		vis[t] = 1
		if color == 'a':
			A.add(t)
			p = 'b'
		else:
			B.add(t)
			p = 'a'
		for i in G[t]:
			if not vis[i]:
				st.append((i, p))
			elif vis[i]:
				if color == 'a' and i in A or (color == 'b' and i in B):
					f = 1
(a, b) = ([], [])
for i in range(1, n + 1):
	if vis[i] or i not in G:
		continue
	(A, B) = (set(), set())
	hello(i)
	a += list(A)
	b += list(B)
if f:
	print(-1)
	exit()
print(len(a))
print(*a)
print(len(b))
print(*b)


import io, os, sys, math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
edges = []
for i in range(m):
	(s, e) = map(int, input().split())
	adj[s].append(e)
	adj[e].append(s)
	edges.append((s, e))
visited = [3] * (n + 1)

@bootstrap
def dfs(node, old):
	if visited[node] != 3:
		yield
	new = (old + 1) % 2
	visited[node] = new
	for i in adj[node]:
		yield dfs(i, new)
	yield
for i in range(1, n + 1):
	if visited[i] == 3:
		dfs(i, 0)
f = True
for (s, e) in edges:
	if visited[s] == visited[e]:
		print(-1)
		f = False
		break
if f:
	ans1 = []
	ans2 = []
	for i in range(1, n + 1):
		if visited[i] == 0:
			ans1.append(i)
		else:
			ans2.append(i)
	print(len(ans1))
	print(*ans1)
	print(len(ans2))
	print(*ans2)


from __future__ import division, print_function
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p1
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def main():
	(n, m) = mi()
	for i in range(m):
		(x, y) = mi()
		graph[x].append(y)
		graph[y].append(x)
	for i in range(1, n + 1):
		if col[i] == -1:
			dfs(i, 1)
	a = []
	b = []
	for i in range(1, n + 1):
		if col[i] == 0:
			a.append(i)
		elif col[i] == 1:
			b.append(i)
	print(len(a))
	print(*a)
	print(len(b))
	print(*b)
sys.setrecursionlimit(100000000)
threading.stack_size(20480000)
thread = threading.Thread(target=main)
thread.start()


(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
used = [-1] * n
ok = True
w = [[], []]

def bfs(start, color):
	used[start] = color
	w[color].append(start)
	q = [start]
	while q != []:
		for u in g[q[0]]:
			if used[u] == -1:
				used[u] = (1 + used[q[0]]) % 2
				w[used[u]].append(u)
				q.append(u)
			elif used[u] == (used[q[0]] + 1) % 2:
				pass
			else:
				return False
		q.pop(0)
	return True
for i in range(n):
	if used[i] == -1:
		if not bfs(i, 0):
			ok = False
			break
if ok:
	for i in range(2):
		print(len(w[i]))
		for j in w[i]:
			print(j + 1, end=' ')
		print()
else:
	print(-1)


(n, m) = map(int, input().split())
g = {x: [] for x in range(1, n + 1)}
for item in range(m):
	(u, v) = map(int, input().split())
	g[v].append(u)
	g[u].append(v)
colors = [None] * (n + 1)

def inversecolor(clr):
	return [0, 1][clr == 0]

def solve(g):
	paths = [x for x in g if g[x] != []]
	currentcolor = 0
	colors[paths[-1]] = currentcolor
	while paths:
		current = paths.pop()
		for targetvertex in g[current]:
			if colors[targetvertex] is None:
				colors[targetvertex] = inversecolor(colors[current])
				paths.append(targetvertex)
			elif colors[targetvertex] != inversecolor(colors[current]):
				return '-1'
	return ([x for (x, item) in enumerate(colors) if item == 1], [x for (x, item) in enumerate(colors) if item == 0])
ans = solve(g)
if ans == '-1':
	print(ans)
else:
	a = ans[0]
	b = ans[1]
	print(len(a))
	print(' '.join([str(x) for x in a]))
	print(len(b))
	print(' '.join([str(x) for x in b]))


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
(n, m) = map(int, input().split())
edges = []
half = 100002
tree = list(range(200005))

def find(x):
	if tree[x] != x:
		tree[x] = find(tree[x])
	return tree[x]

def connect(x, y):
	tree[find(x)] = find(y + half)
	tree[find(y)] = find(x + half)
for _ in range(m):
	(u, v) = map(int, input().split())
	edges.append([u, v])
	connect(u, v)
ans = [set(), set()]
s = {}
for (u, v) in edges:
	(fu, fv) = map(find, (u, v))
	if fu == fv:
		print(-1)
		exit(0)
	elif fu in s and fv in s:
		ans[s[fu]].add(u)
		ans[s[fv]].add(v)
	elif fv in s:
		ans[s[fv]].add(v)
		ans[1 - s[fv]].add(u)
		s[fu] = 1 - s[fv]
	elif fu in s:
		ans[s[fu]].add(u)
		ans[1 - s[fu]].add(v)
		s[fv] = 1 - s[fu]
	else:
		ans[0].add(u)
		ans[1].add(v)
		s[fu] = 0
		s[fv] = 1
print(len(ans[0]))
print(*ans[0])
print(len(ans[1]))
print(*ans[1])


from collections import deque

class CodeforcesTask687ASolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.edges = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.edges.append([int(y) for y in input().split(' ')])

	def process_task(self):
		graph = [[] for x in range(self.n_m[0])]
		for edge in self.edges:
			graph[edge[0] - 1].append(edge[1])
			graph[edge[1] - 1].append(edge[0])
		partite1 = set()
		partite2 = set()
		visited = [False] * self.n_m[0]
		for x in range(self.n_m[0]):
			if not visited[x] and graph[x]:
				to_visit = deque([(x + 1, True)])
				can = True
				while to_visit:
					visiting = to_visit.popleft()
					visited[visiting[0] - 1] = True
					if visiting[1] and visiting[0] in partite2:
						can = False
						break
					elif not visiting[1] and visiting[0] in partite1:
						can = False
						break
					elif visiting[1]:
						if visiting[0] not in partite1:
							partite1.add(visiting[0])
							to_visit.extend([(x, not visiting[1]) for x in graph[visiting[0] - 1]])
					elif visiting[0] not in partite2:
						partite2.add(visiting[0])
						to_visit.extend([(x, not visiting[1]) for x in graph[visiting[0] - 1]])
		for edge in self.edges:
			if edge[0] in partite1 and edge[1] in partite1:
				can = False
			elif edge[0] in partite2 and edge[1] in partite2:
				can = False
		if can:
			self.result = '{0}\n{1}\n{2}\n{3}'.format(len(partite1), ' '.join([str(x) for x in list(partite1)]), len(partite2), ' '.join([str(x) for x in list(partite2)]))
		else:
			self.result = '-1'

	def get_result(self):
		return self.result
Solution = CodeforcesTask687ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


M = lambda : map(int, input().split())
(n, m) = M()
graph = [set() for i in range(n)]
for _ in range(m):
	(a, b) = M()
	graph[a - 1].add(b - 1)
	graph[b - 1].add(a - 1)
visited = [-1 for i in range(n)]
stack = []
for i in range(n):
	if visited[i] == -1 and len(graph[i]) > 0:
		visited[i] = True
		stack += [i]
		while stack:
			x = stack.pop()
			for j in graph[x]:
				if visited[j] == visited[x]:
					print(-1)
					exit(0)
				if visited[j] == -1:
					visited[j] = not visited[x]
					stack += [j]
A = []
B = []
for i in range(len(visited)):
	if visited[i] == True:
		A.append(i + 1)
	elif visited[i] == False:
		B.append(i + 1)
print(len(A))
print(*A)
print(len(B))
print(*B)