You have a simple undirected graph consisting of $n$ vertices and $m$ edges. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let's make a definition.

Let $v_1$ and $v_2$ be two some nonempty subsets of vertices that do not intersect. Let $f(v_{1}, v_{2})$ be true if and only if all the conditions are satisfied:  There are no edges with both endpoints in vertex set $v_1$.  There are no edges with both endpoints in vertex set $v_2$.  For every two vertices $x$ and $y$ such that $x$ is in $v_1$ and $y$ is in $v_2$, there is an edge between $x$ and $y$. 

Create three vertex sets ($v_{1}$, $v_{2}$, $v_{3}$) which satisfy the conditions below;  All vertex sets should not be empty.  Each vertex should be assigned to only one vertex set.  $f(v_{1}, v_{2})$, $f(v_{2}, v_{3})$, $f(v_{3}, v_{1})$ are all true. 

Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.


-----Input-----

The first line contains two integers $n$ and $m$ ($3 \le n \le 10^{5}$, $0 \le m \le \text{min}(3 \cdot 10^{5}, \frac{n(n-1)}{2})$) — the number of vertices and edges in the graph.

The $i$-th of the next $m$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le n$) — it means there is an edge between $a_{i}$ and $b_{i}$. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.


-----Output-----

If the answer exists, print $n$ integers. $i$-th integer means the vertex set number (from $1$ to $3$) of $i$-th vertex. Otherwise, print $-1$.

If there are multiple answers, print any.


-----Examples-----
Input
6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

Output
1 2 2 3 3 3 
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
-1



-----Note-----

In the first example, if $v_{1} = \{ 1 \}$, $v_{2} = \{ 2, 3 \}$, and $v_{3} = \{ 4, 5, 6 \}$ then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like "2 3 3 1 1 1" will be accepted as well. [Image] 

In the second example, it's impossible to make such vertex sets.

Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

String algorithms

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
(n, m) = map(int, input().split())
d = {}
a = [['0'] for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	a[u].append(str(v) + '*')
	a[v].append(str(u) + '*')
count = 1
for i in range(1, n + 1):
	if len(a[i]) == 1:
		print('-1')
		return
	a[i].sort()
for i in range(1, n + 1):
	a[i] = ''.join(a[i])
for i in range(1, n + 1):
	if a[i] not in d:
		d[a[i]] = count
		count += 1
if len(d) != 3:
	print('-1')
	return
for i in range(1, n + 1):
	print(d[a[i]], end=' ')


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

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

def BFS(s, adj):
	parent = {s: None}
	color = [-1] * len(adj)
	color[s] += 1
	u = [s]
	while u:
		nextu = []
		for i in u:
			for v in adj[i]:
				if v not in parent:
					color[v] = (color[i] + 1) % 3
					parent[v] = i
					nextu.append(v)
				elif color[v] == color[i]:
					color[v] = (color[v] + 1) % 3
		u = nextu.copy()
	for i in range(len(adj)):
		color[i] += 1
	return color
(n, m) = lin()
adj = [[] for i in range(n)]
for _ in range(m):
	(i, j) = lin()
	adj[i - 1].append(j - 1)
	adj[j - 1].append(i - 1)
sol = BFS(0, adj)
c1 = [0, 0, 0]
for i in sol:
	if i == 0:
		print(-1)
		return
	c1[i - 1] += 1
ch = [[0 for i in range(3)] for j in range(3)]
for v in range(n):
	for u in adj[v]:
		ch[sol[v] - 1][sol[u] - 1] += 1
		if sol[v] == sol[u]:
			print(-1)
			return
a12 = ch[0][1] + ch[1][0]
a13 = ch[0][2] + ch[2][0]
a23 = ch[1][2] + ch[2][1]
if a12 == 2 * c1[0] * c1[1] and a13 == 2 * c1[0] * c1[2] and (a23 == 2 * c1[1] * c1[2]):
	print(*sol)
else:
	print(-1)


(n, m) = map(int, input().split())
EE = []
if m < 3:
	print(-1)
else:
	edge = [[] for i in range(n)]
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
	EE.append([a - 1, b - 1])
	for i in range(m - 1):
		(x, y) = map(int, input().split())
		edge[x - 1].append(y - 1)
		edge[y - 1].append(x - 1)
		EE.append([x - 1, y - 1])
	c = 0
	for i in range(n):
		if a - 1 in edge[i] and b - 1 in edge[i]:
			c = i + 1
			break
	if c == 0:
		print(-1)
	else:
		Ans = [0] * n
		Ans[a - 1] = 1
		Ans[b - 1] = 2
		Ans[c - 1] = 3
		flg = True
		C = [1] * 3
		for i in range(n):
			if Ans[i] != 0:
				continue
			else:
				E = edge[i]
				if a - 1 in E and b - 1 in E and (c - 1 not in E):
					Ans[i] = 3
					C[2] += 1
				elif a - 1 in E and b - 1 not in E and (c - 1 in E):
					Ans[i] = 2
					C[1] += 1
				elif a - 1 not in E and b - 1 in E and (c - 1 in E):
					Ans[i] = 1
					C[0] += 1
				else:
					print(-1)
					flg = False
					break
		if flg:
			T = [0] * 3
			for (x, y) in EE:
				(xx, yy) = (Ans[x], Ans[y])
				if xx == yy:
					print(-1)
					flg = False
					break
				elif xx == 1 and yy == 2:
					T[0] += 1
				elif xx == 2 and yy == 1:
					T[0] += 1
				elif xx == 1 and yy == 3:
					T[1] += 1
				elif xx == 3 and yy == 1:
					T[1] += 1
				else:
					T[2] += 1
		if flg:
			if T[0] == C[0] * C[1] and T[1] == C[0] * C[2] and (T[2] == C[1] * C[2]):
				print(*Ans)
			else:
				print(-1)


3
import math
import os
import sys
DEBUG = 'DEBUG' in os.environ

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

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)

def solve(N, M, G):
	A = {}
	for i in range(N):
		t = frozenset(G[i])
		if t not in A:
			A[t] = set([i])
		else:
			A[t].add(i)
	if len(A) != 3:
		return None
	((a1, v1), (a2, v2), (a3, v3)) = A.items()
	v1 = frozenset(v1)
	v2 = frozenset(v2)
	v3 = frozenset(v3)
	if a1 != v2 | v3 or a2 != v3 | v1 or a3 != v1 | v2:
		return None
	ans = [0] * N
	for v in v1:
		ans[v] = 1
	for v in v2:
		ans[v] = 2
	for v in v3:
		ans[v] = 3
	return ans

def main():
	(N, M) = [int(e) for e in inp().split()]
	G = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = [int(e) - 1 for e in inp().split()]
		G[a].append(b)
		G[b].append(a)
	ans = solve(N, M, G)
	if not ans:
		print('-1')
	else:
		print(*ans)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
s1 = {1}
s2 = set()
s3 = set()

def checkbi(hash, node):
	queue = [node]
	while queue != []:
		z = queue.pop(0)
		if z in s1:
			yo = 1
		if z in s2:
			yo = 0
		if z in s3:
			yo = 3
		for i in hash[z]:
			if i not in s1 and i not in s2 and (i not in s3):
				if yo == 1:
					s2.add(i)
				else:
					s1.add(i)
				bool[i] = True
				queue.append(i)
			if i in s3 and (yo == 1 or yo == 0):
				continue
			elif i in s3 and yo == 3:
				return -1
			elif i in s1 and yo == 1 or (i in s2 and yo == 0):
				if i not in s3:
					if i in s1:
						s1.remove(i)
					else:
						s2.remove(i)
					bool[i] = True
					queue.append(i)
					s3.add(i)
				else:
					return -1
	return 1
hash = defaultdict(set)
(n, m) = map(int, input().split())
for i in range(m):
	(a, b) = map(int, input().split())
	hash[a].add(b)
	hash[b].add(a)
bool = defaultdict(bool)
for i in range(1, n + 1):
	if bool[i] == False:
		z = checkbi(hash, 1)
		if z == -1:
			print(-1)
			exit()
if len(s1) + len(s2) + len(s3) != n:
	print(-1)
	exit()
for i in s3:
	z = hash[i]
	if hash[i] & s1 != s1 or hash[i] & s2 != s2:
		print(-1)
		exit()
for i in s2:
	z = hash[i]
	if hash[i] & s1 != s1 or hash[i] & s3 != s3:
		print(-1)
		exit()
for i in s1:
	z = hash[i]
	if hash[i] & s2 != s2 or hash[i] & s3 != s3:
		print(-1)
		exit()
ans = []
if s1 == set():
	print(-1)
	exit()
if s2 == set():
	print(-1)
	exit()
if s3 == set():
	print(-1)
	exit()
for i in range(1, n + 1):
	if i in s1:
		ans.append(1)
	elif i in s2:
		ans.append(2)
	else:
		ans.append(3)
print(*ans)


def type_(list_v, group):
	cnt_0 = 0
	cnt_1 = 0
	for v in list_v:
		if v in group:
			cnt_1 += 1
		else:
			cnt_0 += 1
	if cnt_1 == len(group):
		return 1
	if cnt_0 == len(list_v):
		return 0
	return 2

def is_all_type_1(ex_index, list_group, v):
	for (i, group) in list(list_group.items()):
		if i == ex_index:
			continue
		if type_(g[v], group) != 1:
			return False
	return True

def check(v, list_group):
	t = None
	for (i, group) in list(list_group.items()):
		t = type_(g[v], group)
		if t == 0 or t == 2:
			if t == 0:
				if is_all_type_1(i, list_group, v) == True:
					group[v] = 1
				else:
					return 2
			return t
	return t
group = {}

def process(g):
	for v in g:
		if len(group) == 0:
			group[0] = {}
			group[0][v] = 1
			continue
		t = check(v, group)
		if t == 2:
			return -1
		if t == 1:
			if len(group) == 3:
				return -1
			group[len(group)] = {}
			group[len(group) - 1][v] = 1
	return group
g = {}
(n, m) = list(map(int, input().split()))
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	if u not in g:
		g[u] = []
	if v not in g:
		g[v] = []
	g[u].append(v)
	g[v].append(u)
ans = process(g)
if ans == -1 or len(ans) < 3:
	print(-1)
else:
	pr = [0] * n
	cnt = 0
	for (k, gr) in list(group.items()):
		for v in gr:
			cnt += 1
			pr[v - 1] = str(k + 1)
	if cnt == n:
		print(' '.join(pr))
	else:
		print(-1)


from sys import stdin
input = stdin.readline
(v, e) = map(int, input().split())
d = {}
for i in range(1, v + 1):
	d[i] = []
for ed in range(e):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
for i in d:
	d[i].sort()
sas = {}
for i in d:
	sas[tuple(d[i])] = 0
if len(sas) != 3:
	print(-1)
else:
	nbs = []
	for i in sas:
		nbs.append(set(i))
	a = nbs[0].intersection(nbs[1])
	b = nbs[0].intersection(nbs[2])
	c = nbs[1].intersection(nbs[2])
	kol = [0] * (v + 1)
	for i in a:
		kol[i] = 1
	for i in b:
		kol[i] = 2
	for i in c:
		kol[i] = 3
	zer = 0
	for i in range(1, len(kol)):
		if kol[i] == 0:
			zer += 1
			break
	if zer > 0:
		print(-1)
	elif len(a) + len(b) + len(c) != v:
		print(-1)
	else:
		print(*kol[1:])


import collections
from collections import defaultdict
graph1 = defaultdict(list)
(n, m) = map(int, input().split())
groups = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	graph1[u].append(v)
	graph1[v].append(u)
index = [0, 0, 0, 0]
for i in graph1:
	for j in graph1[i]:
		if groups[j - 1] == groups[i - 1]:
			groups[j - 1] = groups[i - 1] + 1
if len(set(groups)) != 3:
	print(-1)
	exit()
for i in groups:
	try:
		index[i] += 1
	except:
		pass
if index[0] * index[1] + index[1] * index[2] + index[2] * index[0] != m:
	print(-1)
	exit()
groups = [p + 1 for p in groups]
print(*groups)


class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

	def __init__(self, arg):
		super().__init__(arg)

	def rangeCountByValue(self, leftVal, rightVal):
		leftCummulative = self.bisect_left(leftVal)
		rightCummulative = self.bisect_left(rightVal + 1)
		return rightCummulative - leftCummulative

def main():
	(n, m) = readIntArr()
	adj = [set() for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = readIntArr()
		adj[u].add(v)
		adj[v].add(u)
	v1 = set()
	v2 = set()
	v3 = set()
	v1.add(1)
	taken = {1}
	for i in range(2, n + 1):
		if i not in adj[1]:
			v1.add(i)
			taken.add(i)
	others = set()
	for i in range(1, n + 1):
		if i not in taken:
			others.add(i)
	if len(others) == 0:
		print(-1)
		return
	node2 = others.pop()
	v2.add(node2)
	for i in range(1, n + 1):
		if i in taken:
			continue
		if i not in adj[node2]:
			v2.add(i)
			taken.add(i)
	for i in range(1, n + 1):
		if i not in taken:
			v3.add(i)
	if len(v3) == 0:
		print(-1)
		return

	def checkSet(v1):
		for u in v1:
			for v in adj[u]:
				if v in v1:
					return False
		return True
	if not (checkSet(v1) and checkSet(v2) and checkSet(v3)):
		print(-1)
		return
	expectedM = len(v1) * (len(v2) + len(v3)) + len(v2) * len(v3)
	if m != expectedM:
		print(-1)
		return
	ans = [-1] * (n + 1)
	for u in v1:
		ans[u] = 1
	for u in v2:
		ans[u] = 2
	for u in v3:
		ans[u] = 3
	ans.pop(0)
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
E = [set() for i in range(n + 1)]
ECOUNT = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	E[x].add(y)
	E[y].add(x)
	ECOUNT[x] += 1
	ECOUNT[y] += 1
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
SCORE = 0
for i in range(1, n + 1):
	if find(i) == i:
		SCORE += 1
		if SCORE >= 4:
			print(-1)
			sys.exit()
		for j in range(i + 1, n + 1):
			if j in E[i]:
				continue
			else:
				Union(i, j)
FD = [find(i) for i in range(n + 1)]
if len(set(FD[1:])) != 3:
	print(-1)
	sys.exit()
for i in range(n + 1):
	for j in E[i]:
		if FD[i] == FD[j]:
			print(-1)
			sys.exit()
compression_dict = {a: ind for (ind, a) in enumerate(sorted(set(FD)))}
ANS = [compression_dict[a] for a in FD]
VFD = [0, 0, 0]
EFD = [0, 0, 0]
for i in range(1, n + 1):
	VFD[ANS[i] - 1] += 1
	EFD[ANS[i] - 1] += ECOUNT[i]
for i in range(3):
	VS = 0
	for j in range(3):
		if i == j:
			continue
		VS += VFD[i] * VFD[j]
	if EFD[i] == VS:
		continue
	else:
		print(-1)
		sys.exit()
print(*ANS[1:])


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

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

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

def inpl_str():
	return list(sys.stdin.readline().split())
(N, M) = inpl()
if M == 0:
	print(-1)
	return
cnts = [0] * N
lines = defaultdict(set)
for _ in range(M):
	(a, b) = inpl()
	a -= 1
	b -= 1
	cnts[a] += 1
	cnts[b] += 1
	lines[a].add(b)
	lines[b].add(a)
setc = set(cnts)
L = len(setc)
ans = [-1] * N
if L == 1:
	ans[a] = 1
	ans[b] = 2
	for i in range(N):
		if ans[i] != 0:
			if i not in lines[a]:
				ans[i] = 1
			elif i not in lines[b]:
				ans[i] = 2
			else:
				ans[i] = 3
elif L == 2:
	(c1, c2) = list(setc)
	if c1 * 2 + c2 == N * 2:
		i1 = cnts.index(c1)
		i2 = cnts.index(c2)
		for (i, c) in enumerate(cnts):
			if c == c2:
				ans[i] = 2
			elif i not in lines[i1]:
				ans[i] = 1
			else:
				ans[i] = 3
	elif c1 + c2 * 2 == N * 2:
		i1 = cnts.index(c1)
		i2 = cnts.index(c2)
		for (i, c) in enumerate(cnts):
			if c == c1:
				ans[i] = 1
			elif i not in lines[i2]:
				ans[i] = 2
			else:
				ans[i] = 3
	else:
		print(-1)
		return
elif L == 3:
	(c1, c2, c3) = list(setc)
	for (i, c) in enumerate(cnts):
		if c == c1:
			ans[i] = 1
		elif c == c2:
			ans[i] = 2
		elif c == c3:
			ans[i] = 3
else:
	print(-1)
	return
if len(set(ans)) != 3:
	print(-1)
	return
for s in range(N):
	for t in lines[s]:
		if ans[s] == ans[t]:
			print(-1)
			return
print(' '.join(map(str, ans)))


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = [int(item) for item in input().split()]
ab = []
edges = [[] for _ in range(n)]
for i in range(m):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	edges[a].append(b)
	edges[b].append(a)
	ab.append((a, b))
groupA = [1] * n
for (a, b) in ab:
	if a == 0:
		groupA[b] = 0
	elif b == 0:
		groupA[a] = 0
par = None
for (i, item) in enumerate(groupA):
	if item == 0:
		par = i
		break
if par == None:
	print(-1)
	exit()
groupB = [1] * n
for (a, b) in ab:
	if a == par:
		groupB[b] = 0
	elif b == par:
		groupB[a] = 0
par = None
for (i, (p, q)) in enumerate(zip(groupA, groupB)):
	if p == 0 and q == 0:
		par = i
		break
if par == None:
	print(-1)
	exit()
groupC = [1] * n
for (a, b) in ab:
	if a == par:
		groupC[b] = 0
	elif b == par:
		groupC[a] = 0
sumA = sum(groupA)
sumB = sum(groupB)
sumC = sum(groupC)
e_abc = [0, n - sumA, n - sumB, n - sumC]
edge_num = sumA * sumB + sumB * sumC + sumC * sumA
if edge_num != m:
	print(-1)
	exit()
setA = set()
setB = set()
setC = set()
group = [groupA, groupB, groupC]
ret = []
for (i, (ga, gb, gc)) in enumerate(zip(groupA, groupB, groupC)):
	total = ga + gb + gc
	if total != 1:
		print(-1)
		exit()
	if ga:
		ret.append(1)
		setA.add(i)
	elif gb:
		ret.append(2)
		setB.add(i)
	else:
		ret.append(3)
		setC.add(i)
s_ABC = [set(), setA, setB, setC]
for (i, item) in enumerate(ret):
	if e_abc[item] != len(edges[i]):
		print(-1)
		exit()
	for node in edges[i]:
		if node in s_ABC[item]:
			print(-1)
			exit()
print(' '.join([str(item) for item in ret]))


import sys
readline = sys.stdin.readline
(n, m) = map(int, input().split())
ans = True
graph = [[] for i in range(n)]
for _ in range(m):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
s1 = set(graph[0])
s2 = set()
if len(graph[0]) != 0:
	s2 = set(graph[graph[0][0]])
else:
	ans = False
s3 = set(s1.union(s2)) - (s1 & s2)
s21 = s2 & s3
s22 = s1 & s3
s23 = s2 & s1
if len(s21) + len(s22) + len(s23) != n:
	ans = False
if len(s21) == 0 or len(s22) == 0 or len(s23) == 0:
	ans = False
if ans:
	for x in s21:
		if set(graph[x]) != s1:
			ans = False
			break
if ans:
	for x in s22:
		if set(graph[x]) != s2:
			ans = False
			break
if ans:
	for x in s23:
		if set(graph[x]) != s3:
			ans = False
			break
if not ans:
	print(-1)
else:
	for i in range(n):
		if i in s21:
			print(1, end=' ')
		elif i in s22:
			print(2, end=' ')
		else:
			print(3, end=' ')


import sys
(n, m) = [int(x) for x in input().split()]
d = {i: [] for i in range(n)}
for _ in range(m):
	(ai, bi) = [int(x) for x in input().split()]
	d[ai - 1].append(bi - 1)
	d[bi - 1].append(ai - 1)
which_set = [None for _ in range(n)]
SET_B_OR_C = 0
SET_A = 1
SET_B = 2
SET_C = 3
for x in d[0]:
	which_set[x] = SET_B_OR_C
for x in range(n):
	if which_set[x] is None:
		which_set[x] = SET_A
if not d[0]:
	print(-1)
	sys.exit(0)
for x in d[d[0][0]]:
	if which_set[x] == SET_B_OR_C:
		which_set[x] = SET_B
	elif which_set[x] == SET_A:
		continue
	else:
		print(-1)
		sys.exit(0)
for x in range(n):
	if which_set[x] == SET_B_OR_C:
		which_set[x] = SET_C
(num_A, num_B, num_C) = (0, 0, 0)
for x in which_set:
	if x == SET_A:
		num_A += 1
	if x == SET_B:
		num_B += 1
	if x == SET_C:
		num_C += 1
if num_A == 0 or num_B == 0 or num_C == 0:
	print(-1)
	sys.exit(0)

def same_set(x, y):
	return which_set[x] == which_set[y]
for x in d:
	for y in d[x]:
		if same_set(x, y):
			print(-1)
			sys.exit(0)
expected_num_edges = (num_A * num_B + num_B * num_C + num_A * num_C) * 2
if sum((len(d[x]) for x in d)) != expected_num_edges:
	print(-1)
	sys.exit(0)
print(*which_set)


(n, m) = map(int, input().split())
ad = [[] for _ in range(n)]
es = []
for _ in range(m):
	(v, u) = map(int, input().split())
	v -= 1
	u -= 1
	es.append((min(v, u), max(v, u)))
es = sorted(es, key=lambda x: (x[0], x[1]))
for e in es:
	(v, u) = e
	ad[v].append(str(u))
	ad[u].append(str(v))
ad = [''.join(a) for a in ad]
d = {}
for t in ad:
	if t not in d:
		d[t] = str(len(d) + 1)
	if len(d) > 3:
		print(-1)
		exit()
if len(d) != 3:
	print(-1)
	exit()
ans = []
for t in ad:
	ans.append(d[t])
print(' '.join(ans))


import sys
input = lambda : sys.stdin.readline().rstrip()
(N, M) = list(map(int, input().split()))
E = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
inf = 1 << 20
(A, B, C) = ([], [], [])
X = [0] * N
for a in E[0]:
	X[a] = 1
A = [i for i in range(N) if X[i] == 0]
b = min([i for i in range(N) if X[i] == 1] + [inf])
if b < inf:
	for a in E[b]:
		if X[a] == 1:
			X[a] = 2
	B = [i for i in range(N) if X[i] == 1]
c = min([i for i in range(N) if X[i] == 2] + [inf])
if c < inf:
	for a in E[c]:
		if X[a] == 2:
			X[a] = 3
	C = [i for i in range(N) if X[i] == 2]
if max(X) == 2 and len(A) * len(B) * len(C) and (len(A) + len(B) + len(C) == N) and (len(A) * len(B) + len(B) * len(C) + len(A) * len(C) == M):
	f = 0
	for i in range(N):
		for j in E[i]:
			if X[i] == X[j]:
				f = 1
				break
		if f:
			break
	if f:
		print(-1)
	else:
		print(*[x + 1 for x in X])
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [set() for i in range(n)]
cnt_e = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].add(v - 1)
	g[v - 1].add(u - 1)
	cnt_e[u - 1] += 1
	cnt_e[v - 1] += 1
group = [i for i in range(n)]

def find(x):
	while group[x] != x:
		x = group[x]
	return x

def union(x, y):
	if find(x) != find(y):
		group[find(x)] = group[find(y)] = min(find(x), find(y))
score = 0
for i in range(n):
	if find(i) == i:
		score += 1
		if score >= 6:
			print(-1)
			exit()
		for j in range(i + 1, n):
			if not j in g[i]:
				union(i, j)
fd = [find(i) for i in range(n)]
if len(set(fd)) != 3:
	print(-1)
	exit()
for i in range(n):
	for j in g[i]:
		if fd[i] == fd[j]:
			print(-1)
			exit()
num = list(set(fd))
ans = [0] * n
cnt_v = [0] * 3
cnt_zisu = [0] * 3
for i in range(n):
	if fd[i] == num[0]:
		ans[i] = 1
		cnt_v[0] += 1
		cnt_zisu[0] += cnt_e[i]
	elif fd[i] == num[1]:
		ans[i] = 2
		cnt_v[1] += 1
		cnt_zisu[1] += cnt_e[i]
	else:
		ans[i] = 3
		cnt_v[2] += 1
		cnt_zisu[2] += cnt_e[i]
flag = True
flag &= cnt_v[0] * cnt_v[1] + cnt_v[0] * cnt_v[2] == cnt_zisu[0]
flag &= cnt_v[0] * cnt_v[1] + cnt_v[1] * cnt_v[2] == cnt_zisu[1]
flag &= cnt_v[2] * cnt_v[1] + cnt_v[0] * cnt_v[2] == cnt_zisu[2]
if flag:
	print(*ans)
else:
	print(-1)


import sys
(n, m) = [int(i) for i in sys.stdin.readline().split()]
group = [0] * n
data = [set() for i in range(n)]
gi = 0
for i in range(m):
	(a, b) = [int(j) - 1 for j in sys.stdin.readline().split()]
	data[a].add(b)
	data[b].add(a)
for i in range(n):
	if group[i] == 0:
		gi += 1
		if gi == 4:
			print(-1)
			exit()
		nei = data[i]
		for j in range(n):
			if j not in nei:
				group[j] = gi
cnt = [0, 0, 0, 0]
cnt[1] = group.count(1)
cnt[2] = group.count(2)
cnt[3] = n - cnt[1] - cnt[2]
for i in range(1, 4):
	if cnt[i] <= 0:
		print(-1)
		exit()
amount = 0
for (a, b) in [(1, 2), (2, 3), (1, 3)]:
	amount += cnt[a] * cnt[b]
if amount != m:
	print(-1)
	exit()
for a in range(1, 4):
	for i in range(n):
		if group[i] == a:
			for neib in data[i]:
				c = group[neib]
				if c == a:
					print(-1)
					exit()
print(*group)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

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

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

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

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	(n, m) = sep()
	g = [[] for i in range(n)]
	for i in range(m):
		(a, b) = sep()
		a -= 1
		b -= 1
		g[a].append(b)
		g[b].append(a)
	hash = {}
	for i in range(n):
		neigh = []
		for j in g[i]:
			neigh.append(j)
		neigh = sorted(neigh)
		curr = ''
		for j in neigh:
			curr += str(j) + ' '
		if curr in hash:
			hash[curr].append(i)
		else:
			hash[curr] = [i]
		if len(hash) > 3:
			print(-1)
			return
	col = [-1] * n
	ll = []
	if len(hash) == 3:
		curr = 1
		for i in hash:
			ll.append(len(hash[i]))
			for j in hash[i]:
				col[j] = curr
			curr += 1
	else:
		print(-1)
		return
	if m != ll[0] * ll[1] + ll[0] * ll[2] + ll[1] * ll[2]:
		print(-1)
		return
	print(' '.join((str(col[i]) for i in range(len(col)))))
testcase(1)


try:
	from string_source import string_source
except ImportError:
	source = input
from collections import defaultdict

def complete_bipartite(n, edges):
	if not edges:
		return False
	neighbors = defaultdict(set, {})
	for (e1, e2) in edges:
		neighbors[e1].add(e2)
		neighbors[e2].add(e1)
	(s1, s2) = edges[0]
	groups = [None, None, None]
	groups[2] = neighbors[s1].intersection(neighbors[s2])
	groups[1] = neighbors[s1].difference(neighbors[s2])
	groups[0] = set(neighbors).difference(groups[2], groups[1])

	def get_group(node):
		return next((idx for (idx, g) in enumerate(groups) if node in g))
	sizes = [len(g) for g in groups]
	if sum((len(g) for g in groups)) < n:
		return False
	if any((len(g) == 0 for g in groups)):
		return False
	for (e1, e2) in edges:
		if get_group(e1) == get_group(e2):
			return False
	answer = [0] * n
	for (node, neigh) in neighbors.items():
		g = get_group(node)
		if sum((s for (idx, s) in enumerate(sizes) if idx != g)) != len(neigh):
			return False
		answer[node - 1] = g + 1
	return answer

def answer(source):
	(n, m) = map(int, source().strip().split())
	edges = [[int(k) for k in source().strip().split()] for _ in range(m)]
	a = complete_bipartite(n, edges)
	if not a:
		print(-1)
	else:
		print(' '.join(map(str, a)))
answer(input)
if False:
	answer(string_source('6 11\n    1 2\n    1 3\n    1 4\n    1 5\n    1 6\n    2 4\n    2 5\n    2 6\n    3 4\n    3 5\n    3 6'))
	answer(string_source('4 6\n    1 2\n    1 3\n    1 4\n    2 3\n    2 4\n    3 4'))


def exitprint():
	print(-1)
	exit(0)
(n, m) = list(map(int, input().split()))
al = [list() for _ in range(n)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	al[u - 1].append(v - 1)
	al[v - 1].append(u - 1)
for i in range(n):
	al[i] = frozenset(al[i])
a = {}
k = 1
ans = []
for i in range(n):
	if len(al[i]) == 0:
		exitprint()
	if al[i] in a:
		ans.append(a[al[i]])
	else:
		a[al[i]] = k
		k += 1
		ans.append(a[al[i]])
	if len(a) > 3:
		exitprint()
if len(a) < 3:
	exitprint()
print(*ans)


(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
if len(G[0]) < 2:
	print(-1)
	return
res = [1] * n
for a in G[0]:
	res[a] = 2
a2 = G[0][0]
for b in G[a2]:
	if res[b] == 2:
		res[b] = 3
sizes = [n - len(G[0]), n - len(G[a2]), len(G[0]) + len(G[a2]) - n]
if 0 in sizes:
	print(-1)
	return
for i in range(n):
	g = res[i]
	s = sizes[g - 1]
	if len(G[i]) != n - s:
		print(-1)
		return
	for j in G[i]:
		if res[j] == g:
			print(-1)
			return
print(*res)


def main():
	(vertex, edge) = map(int, input().split())
	data = {key: set() for key in range(1, vertex + 1)}
	for i in range(edge):
		(a, b) = map(int, input().split())
		data[a].add(b)
		data[b].add(a)
	v = []
	temp = [None, None, None]
	for node in data.values():
		if temp[0] and temp[1] and temp[2]:
			break
		elif temp[0] is None:
			temp[0] = node
		elif temp[1] is None and node != temp[0]:
			temp[1] = node
		elif temp[2] is None and node != temp[1] and (node != temp[0]):
			temp[2] = node
	dec = False
	if temp[0] and temp[1] and temp[2]:
		for i in range(1, vertex + 1):
			if data[i] == temp[0]:
				v.append(1)
			elif data[i] == temp[1]:
				v.append(2)
			elif data[i] == temp[2]:
				v.append(3)
			else:
				dec = True
				break
	else:
		dec = True
	if dec:
		print(-1)
	else:
		for team in v:
			print(team, end=' ')
main()


import sys

def fill(graph, n):
	dp = [[True, True, True] for _ in range(n + 1)]
	l = [-1 for i in range(n + 1)]
	from collections import defaultdict
	vis = defaultdict(int)
	(count1, count2, count3) = (0, 0, 0)
	for i in graph:
		if dp[i][0]:
			(l[i], count1) = (1, count1 + 1)
			vis[i] = 1
			for j in graph[i]:
				dp[j][0] = False
		elif dp[i][1]:
			l[i] = 2
			count2 += 1
			vis[i] = 2
			for j in graph[i]:
				dp[j][1] = False
		elif dp[i][2]:
			l[i] = 3
			count3 += 1
			vis[i] = 3
			for j in graph[i]:
				dp[j][2] = False
		else:
			return [-1]
	if count1 == 0 or count2 == 0 or count3 == 0:
		return [-1]
	if count1 + count2 + count3 != n:
		return [-1]
	if count1 * count2 + count2 * count3 + count1 * count3 != m:
		return [-1]
	l.pop(0)
	for i in l:
		if i == -1:
			return [-1]
	return l
(n, m) = map(int, sys.stdin.readline().split())
from collections import defaultdict
graph = defaultdict(list)
for i in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	graph[a].append(b)
	graph[b].append(a)
k = fill(graph, n)
print(*k)


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
(n, m) = map(int, input().split())
gr = [set() for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	gr[a - 1].add(b - 1)
	gr[b - 1].add(a - 1)
v = [False for i in range(n)]
group = [-1 for i in range(n)]
d = 1
i = 0
while d < 4:
	if v[i]:
		continue
	v[i] = True
	group[i] = d
	for j in range(n):
		if j not in gr[i]:
			group[j] = d
			v[j] = True
	d += 1
	if False in v:
		i = v.index(False)
	else:
		break
if False in v:
	print(-1)
else:
	(a, b, c) = (group.count(1), group.count(2), group.count(3))
	t = True
	for i in range(n):
		for j in gr[i]:
			if group[i] == group[j]:
				t = False
				break
	if t and a * b + b * c + a * c == m and (a != 0) and (b != 0) and (c != 0):
		print(*group)
	else:
		print(-1)


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for _ in range(N)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			return self.find(self.parent[x])

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px == py:
			return
		if self.size[px] < self.size[py]:
			self.parent[px] = py
			self.size[py] += self.size[px]
		else:
			self.parent[py] = px
			self.size[px] += self.size[py]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def connectedNum(self, x):
		return self.size[self.find(x)]

	def component_NUM(self):
		par = set()
		for i in self.parent:
			par.add(self.find(i))
		return len(par)
(N, M) = list(map(int, input().split()))
adj = [set() for _ in range(N)]
Un = UnionFind(N)
for _ in range(M):
	(a, b) = [int(x) - 1 for x in input().split()]
	adj[a].add(b)
	adj[b].add(a)
added = set()
representative = set()
for i in range(N):
	if i in added:
		continue
	added.add(i)
	representative.add(i)
	for j in range(i + 1, N):
		if j in added:
			continue
		if adj[i] == adj[j]:
			added.add(j)
			Un.union(i, j)
	if len(representative) > 3:
		print(-1)
		return
if Un.component_NUM() == 3:
	group = {}
	ans = []
	for p in range(N):
		par = Un.find(p)
		if par not in list(group.keys()):
			group[par] = len(group) + 1
		ans.append(group[par])
	print(' '.join(map(str, ans)))
else:
	print(-1)


from collections import defaultdict, deque

def threeSets(vs, es, d):
	sets = [3] * vs
	s1 = 0
	dist = [float('inf')] * vs
	sets[s1] = 1
	dist[s1] = 0
	queue = deque([s1])
	while queue:
		v1 = queue.pop()
		for v2 in d[v1]:
			if dist[v2] > dist[v1] + 1:
				dist[v2] = dist[v1] + 1
				queue.appendleft(v2)
	for i in range(vs):
		if dist[i] > 2:
			return [-1]
		elif dist[i] == 2:
			sets[i] = 1
	try:
		s2 = sets.index(3)
	except:
		return [-1]
	dist = [float('inf')] * vs
	sets[s2] = 2
	dist[s2] = 0
	queue = deque([s2])
	while queue:
		v1 = queue.pop()
		for v2 in d[v1]:
			if dist[v2] > dist[v1] + 1:
				dist[v2] = dist[v1] + 1
				queue.appendleft(v2)
	for i in range(vs):
		if dist[i] > 2:
			return [-1]
		elif dist[i] == 2:
			if sets[i] == 1:
				return [-1]
			else:
				sets[i] = 2
	VS = [set() for i in range(3)]
	for i in range(vs):
		g = sets[i] - 1
		VS[g].add(i)
	for V in VS:
		if not len(V):
			return [-1]
	for v1 in VS[0]:
		for v2 in VS[1]:
			if v2 not in d[v1]:
				return [-1]
		for v2 in VS[2]:
			if v2 not in d[v1]:
				return [-1]
	for v1 in VS[1]:
		for v2 in VS[2]:
			if v2 not in d[v1]:
				return [-1]
	valid_es = len(VS[0]) * len(VS[1]) + len(VS[0]) * len(VS[2]) + len(VS[1]) * len(VS[2])
	return sets if es == valid_es else [-1]
d = defaultdict(set)
(vs, es) = list(map(int, input().split()))
for _ in range(es):
	(v1, v2) = list(map(int, input().split()))
	v1 -= 1
	v2 -= 1
	d[v1].add(v2)
	d[v2].add(v1)
print(*threeSets(vs, es, d))


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

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

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

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

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

def geta():
	return int(input())

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

def solve():
	(n, m) = geti()
	edges = dd(list)
	color = [0] * (n + 1)
	for i in range(m):
		(u, v) = geti()
		edges[u].append(v)
		edges[v].append(u)
	for i in edges:
		color[i] = 1
		for node in edges[i]:
			color[node] = 2
		break
	for i in edges:
		if color[i] == 0:
			color[i] = 1
			for node in edges[i]:
				if color[node] != 2:
					return False
	for i in edges:
		if color[i] == 2:
			for node in edges[i]:
				if color[node] == 2:
					color[node] = 3
				elif color[node] == 0:
					return False
			break
	for i in edges:
		if color[i] == 2:
			for node in edges[i]:
				if color[node] != 3 and color[node] != 1:
					return False
	for i in edges:
		if color[i] == 3:
			for node in edges[i]:
				if color[node] == 3 or color[node] == 0:
					return False
	(one, two, three) = (color.count(1), color.count(2), color.count(3))
	for i in edges:
		if color[i] == 1:
			temp2 = temp3 = 0
			for node in edges[i]:
				if color[node] == 2:
					temp2 += 1
				elif color[node] == 3:
					temp3 += 1
				else:
					return False
			if temp2 != two or temp3 != three:
				return False
		if color[i] == 2:
			temp1 = temp3 = 0
			for node in edges[i]:
				if color[node] == 1:
					temp1 += 1
				elif color[node] == 3:
					temp3 += 1
				else:
					return False
			if temp1 != one or temp3 != three:
				return False
	if color.count(0) == 1 and one and two and three:
		return color[1:]
	return False
ans = solve()
if ans:
	print(*ans)
else:
	print(-1)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

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

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, m) = inpl()
e = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = inpl()
	(a, b) = (a - 1, b - 1)
	e[a].append(b)
	e[b].append(a)
se = set()
for i in range(n):
	e[i].sort()
	se.add(tuple(e[i]))
if len(se) != 3:
	print(-1)
else:
	d = {}
	for (i, x) in enumerate(list(se)):
		d[x] = i + 1
	res = [-1] * n
	cnt = [0, 0, 0]
	for i in range(n):
		tmp = d[tuple(e[i])]
		cnt[tmp - 1] += 1
		res[i] = tmp
	for key in list(d):
		ind = d[key]
		if len(key) + cnt[ind - 1] != n:
			print(-1)
			break
	else:
		print(*res)


(n, m) = map(int, input().split())
neigh = [set() for i in range(n + 1)]
total = set(range(1, n + 1))
for i in range(m):
	(a, b) = map(int, input().split())
	neigh[a].add(str(b))
	neigh[b].add(str(a))
for i in range(len(neigh)):
	neigh[i] = frozenset(neigh[i])
numbers = dict()
count = 0
r = []
for i in neigh[1:]:
	if i in numbers:
		r.append(numbers[i])
	else:
		if len(i) < 2:
			print(-1)
			exit()
		count += 1
		numbers[i] = count
		r.append(count)
if count != 3:
	print(-1)
	exit()
print(*r)


import sys
input = sys.stdin.readline

def r1():
	return int(input())

def r2():
	return map(int, input().split())
(n, m) = r2()
d = {}
for i in range(1, n + 1):
	d[i] = set()
for i in range(m):
	(x, y) = r2()
	d[x].add(y)
	d[y].add(x)
first = set(range(1, n + 1)) - d[1]
if not d[1]:
	print(-1)
else:
	flag = 1
	for el in first:
		if d[el] != d[1]:
			flag = 0
	if not flag:
		print(-1)
	else:
		i = 2
		while i not in d[1]:
			i += 1
		second = d[i] - first
		third = d[1] - second
		if not second or not third:
			flag = 0
		etalon = first.union(third)
		for el in second:
			if d[el] != etalon:
				flag = 0
		etalon = first.union(second)
		for el in third:
			if d[el] != etalon:
				flag = 0
		if not flag:
			print(-1)
		else:
			for i in range(1, n + 1):
				if i in first:
					print(1, end=' ')
				elif i in second:
					print(2, end=' ')
				else:
					print(3, end=' ')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
tree = [set() for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	tree[a - 1].add(b - 1)
	tree[b - 1].add(a - 1)
check = [-1] * n
seen = [False] * n
now = 1
for i in range(n):
	if not seen[i]:
		for j in range(n):
			if j not in tree[i]:
				check[j] = now
				seen[j] = True
		now += 1
		if now == 5:
			print(-1)
			exit()
if now == 1 or now == 2 or now == 3:
	print(-1)
	exit()
setnum = [set() for i in range(n)]
s = [0] * n
for i in range(n):
	setnum[check[i] - 1].add(i)
	s[check[i] - 1] += 1
for i in range(n):
	if len(tree[i]) + s[check[i] - 1] != n:
		print(-1)
		exit()
	for j in tree[i]:
		if j in setnum[check[i] - 1]:
			print(-1)
			exit()
print(' '.join(map(str, check)))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, g):
	if M < N - 1:
		print(-1)
		return
	mark = [1 for _ in range(N + 1)]
	mark[1] = 1
	mark[0] = 0
	b = 0
	for v in g[1]:
		mark[v] = 2
		b = v
	for v in g[b]:
		if mark[v] == 2:
			mark[v] = 3
	(na, nb, nc) = (mark.count(1), mark.count(2), mark.count(3))
	if M != na * nb + nb * nc + na * nc or any([n == 0 for n in [na, nb, nc]]):
		print(-1)
		return
	ns = [0, na, nb, nc]
	for u in range(1, N + 1):
		v = g[u]
		if len(v) != N - ns[mark[u]]:
			print(-1)
			return
		wc = collections.Counter([mark[x] for x in v])
		for (k, c) in wc.items():
			if c != ns[k]:
				print(-1)
				return
	print(' '.join(map(str, mark[1:])))
(N, M) = map(int, input().split())
g = [[] for _ in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
solve(N, M, g)


def main():
	from array import array
	from sys import stdin, stdout
	(n, m) = list(map(int, stdin.readline().split()))
	inp = {tuple(map(int, stdin.readline().split())) for _ in range(m)}
	ans = array('b', (0,)) * (n + 1)
	ans[1] = 1
	c1 = 1
	c2 = c3 = 0
	i = 1
	for j in range(2, n + 1):
		if (1, j) not in inp:
			ans[j] = 1
			c1 += 1
		else:
			if i == 1:
				i = j
			if (i, j) in inp:
				ans[j] = 2
				c2 += 1
			else:
				ans[j] = 3
				c3 += 1
	if m != c1 * (c2 + c3) + c2 * c3 or not c2:
		stdout.write('-1')
	else:
		for (i, j) in inp:
			if ans[i] == ans[j]:
				stdout.write('-1')
				break
		else:
			stdout.write(' '.join((str(ansi) for ansi in ans if ansi)))
main()


import sys
input = sys.stdin.readline
import collections

def tripartite(n, edges):
	graph = {}
	for i in range(n):
		graph[i] = set()
	for (e1, e2) in edges:
		graph[e1].add(e2)
		graph[e2].add(e1)
	visited = [False] * n
	q = collections.deque()
	q.append(0)
	while q:
		lenq = len(q)
		for _ in range(lenq):
			cur = q.popleft()
			if visited[cur]:
				continue
			visited[cur] = True
			for nei in graph[cur]:
				q.append(nei)
	if not all(visited):
		return [-1]
	colors = [0] * n
	q = collections.deque()
	color = 1
	for i in range(n):
		if colors[i] != 0:
			continue
		q.append(i)
		while q:
			lenq = len(q)
			for _ in range(lenq):
				cur = q.popleft()
				if colors[cur] != 0:
					continue
				colors[cur] = color
				for nei in graph[cur]:
					q.append(nei)
			color = 3 - color
	for i in range(n):
		if colors[i] != 1:
			colors[i] = 0
	for i in range(n):
		if colors[i] != 0:
			continue
		q.append(i)
		color = 2
		while q:
			lenq = len(q)
			for _ in range(lenq):
				cur = q.popleft()
				if colors[cur] != 0:
					if colors[cur] == 1:
						continue
					if colors[cur] == color:
						continue
					if colors[cur] != color:
						return [-1]
				colors[cur] = color
				for nei in graph[cur]:
					q.append(nei)
			color = 5 - color
	if len(set(colors)) < 3:
		return [-1]
	counter = collections.Counter(colors)
	for i in range(n):
		if len(graph[i]) < n - counter[colors[i]]:
			return [-1]
	for i in range(n):
		for nei in graph[i]:
			if colors[i] == colors[nei]:
				return [-1]
	return colors

def main():
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	edges = []
	for _ in range(m):
		(e1, e2) = input().split()
		edges.append((int(e1) - 1, int(e2) - 1))
	print(' '.join(map(str, tripartite(n, edges))))
main()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
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))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	(n, m) = map(int, input().split())
	d = {}
	ans = [-1 for i in range(n + 1)]
	(U, V, Z) = (-1, -1, -1)
	edges = []
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
		edges.append([u, v])
		if i == 0:
			ans[u] = 1
			ans[v] = 2
			U = u
			V = v
		d[u, v] = d[v, u] = 1
	f = 1
	(o, tw, th) = (1, 1, 0)
	for i in range(1, n + 1):
		if (U, i) in d.keys() and (V, i) in d.keys():
			ans[i] = 3
			Z = i
			th += 1
			break
	if Z != -1:
		for i in range(1, n + 1):
			if i != U and i != V and (i != Z):
				if (i, U) in d.keys() and (i, V) in d.keys() and ((i, Z) not in d.keys()):
					ans[i] = 3
					th += 1
				elif (i, U) in d.keys() and (i, V) not in d.keys() and ((i, Z) in d.keys()):
					ans[i] = 2
					tw += 1
				elif (i, U) not in d.keys() and (i, V) in d.keys() and ((i, Z) in d.keys()):
					ans[i] = 1
					o += 1
				else:
					f = 0
	else:
		f = 0
	sums = [o, tw, th]
	k = sum(sums)
	for i in range(1, n + 1):
		if len(adj[i]) != k - sums[ans[i] - 1]:
			f = 0
	for i in edges:
		if ans[i[0]] == -1 or ans[i[1]] == -1:
			f = 0
		if ans[i[0]] == ans[i[1]]:
			f = 0
	if f:
		for i in range(1, n + 1):
			print(ans[i], end=' ')
	else:
		print(-1)
	return
main()


import sys
input = sys.stdin.readline

def r1():
	return int(input())

def r2():
	return map(int, input().split())
(n, m) = r2()
d = {}
for i in range(1, n + 1):
	d[i] = set()
for i in range(m):
	(x, y) = r2()
	d[x].add(y)
	d[y].add(x)
bc = d.get(1, [])
if len(bc) == 0:
	print(-1)
	exit()
ac = d.get(next(iter(bc)), [])
if len(ac) == 0:
	print(-1)
	exit()
c = bc & ac
a = ac - c
b = bc - c
ab = a | b
na = len(a)
nb = len(b)
nc = len(c)
if na + nb + nc != n or not na or (not nb) or (not nc):
	print(-1)
else:
	for x in a:
		if d.get(x, []) != bc:
			print(-1)
			exit()
	for x in b:
		if d.get(x, []) != ac:
			print(-1)
			exit()
	for x in c:
		if d.get(x, []) != ab:
			print(-1)
			exit()
	r = ['' for i in range(n)]
	for x in a:
		r[x - 1] = '1'
	for x in b:
		r[x - 1] = '2'
	for x in c:
		r[x - 1] = '3'
	print(' '.join(r))


def split_group(n):
	for g in range(1, 4):
		first_node = 1
		while first_node <= n and group[first_node] != 0:
			first_node = first_node + 1
		if first_node > n:
			return False
		group[first_node] = g
		group_cnt[g] = group_cnt[g] + 1
		group_mem[g].append(first_node)
		for i in range(1, n + 1):
			if group[i] == 0 and i not in edge[first_node]:
				group[i] = g
				group_cnt[g] = group_cnt[g] + 1
				group_mem[g].append(i)

def judge():
	if group_cnt[1] * group_cnt[2] + group_cnt[2] * group_cnt[3] + group_cnt[3] * group_cnt[1] != m:
		return False
	for g1 in range(1, 3):
		for g2 in range(g1 + 1, 4):
			for node1 in group_mem[g1]:
				for node2 in group_mem[g2]:
					if node1 not in edge[node2]:
						return False
	return True
edge = dict()
(n, m) = [int(c) for c in input().split()]
group = [0] * (n + 1)
group_cnt = [0] * 4
group_mem = [[], [], [], []]
for i in range(n):
	edge[i + 1] = set()
for i in range(m):
	(u, v) = [int(c) for c in input().split()]
	edge[u].add(v)
	edge[v].add(u)
if split_group(n) == False:
	print(-1)
elif judge() == False or m == 0:
	print(-1)
else:
	for node_group in range(1, n + 1):
		print(group[node_group], end=' ')


a = list(map(int, input().split()))
n = a[0]
e = a[1]
g = {}
for itr in range(1, n + 1):
	g[itr] = []
for i in range(e):
	a = list(map(int, input().split()))
	g[a[0]].append(a[1])
	g[a[1]].append(a[0])
for itr in range(1, n + 1):
	g[itr] = frozenset(g[itr])
a = {}
k = 1
res = []
for i in range(1, n + 1):
	if len(g[i]) == 0:
		k = 100
		break
	if g[i] in a:
		res.append(a[g[i]])
	else:
		a[g[i]] = k
		k += 1
		res.append(a[g[i]])
	if len(a) > 3:
		break
if k != 4:
	print(-1)
else:
	print(*res)