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: interview

Starter code:

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


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

ad = [[] for _ in range(n)]

es = []
for _ in range(m):
    v,u = list(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)
        return
if len(d) != 3:
    print(-1)
    return

ans = []
for t in ad:
    ans.append(d[t])
print(' '.join(ans))


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


# python template for atcoder1
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)


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


"""
NTC here
"""
from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10**7)
 
# print("Case #{}: {} {}".format(i, n + m, n * m))
 
 
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:  # runs till u is []
        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)
                else:
                    if 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] #count of 1,2,3
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)] #12,13,23

for v in range(n):
    for u in adj[v]:
        ch[sol[v]-1][sol[u]-1]+=1
#        ch[sol[u]-1][sol[v]-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]
#print(a12,a13,a23,c1,sol)
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())
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)

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

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

groupC = [1] * n
for a, b in ab:
    if a == par:
        groupC[b] = 0
    elif b == par:
        groupC[a] = 0

# Check edge num
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)
    return

# Answer
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)
        return
    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)
        return
    for node in edges[i]:
        if node in s_ABC[item]:
            print(-1)
            return
print(" ".join([str(item) for item in ret]))

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
E=[set() for i in range(n+1)]
ECOUNT=[0]*(n+1)

for i in range(m):
    x,y=list(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>=6:
            print(-1)
            return
            
        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)
    return

for i in range(n+1):
    for j in E[i]:
        if FD[i]==FD[j]:
            print(-1)
            return


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


print(*ANS[1:])




import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
E=[set() for i in range(n+1)]
ECOUNT=[0]*(n+1)

for i in range(m):
    x,y=list(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)
            return
            
        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)
    return

for i in range(n+1):
    for j in E[i]:
        if FD[i]==FD[j]:
            print(-1)
            return


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


print(*ANS[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)
	else:
		if len(a)+len(b)+len(c) !=v:
			print(-1)
		else:
			print(*kol[1:])

# https://codeforces.com/contest/1228/problem/D
# all neightbor in group --> pass 1
# all neighbor not in group --> merge 0
# invalid 2
# WA
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)
# 1,2  3,4  5,6
#6 12
#1 3
#1 4
#2 3
#2 4
#1 5 
#1 6
#2 5
#2 6
#3 5
#3 6
#4 5
#4 6


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
            else:
                if 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
            else:
                if 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
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]:
            #fill
            l[i],count1=1,count1+1
            vis[i]=1
            for j in graph[i]:
                dp[j][0]=False
        elif dp[i][1]:
            #fill
            l[i]=2
            count2+=1
            vis[i]=2
            for j in graph[i]:
                dp[j][1]=False
        elif dp[i][2]:
            #fill
            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=list(map(int,sys.stdin.readline().split()))
from collections import defaultdict
graph=defaultdict(list)
for i in range(m):
    a,b=list(map(int,sys.stdin.readline().split()))
    graph[a].append(b)
    graph[b].append(a)
k=fill(graph,n)
print(*k)


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)

n,m=list(map(int,input().split()))
EE=[]
if m<3:
  print(-1)
else:
  edge = [set() for i in range(n)]
  a,b=list(map(int,input().split()))
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)
  EE.append([a-1,b-1])

  for i in range(m-1):
    x,y=list(map(int,input().split()))
    edge[x-1].add(y-1)
    edge[y-1].add(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)







import sys
input = lambda: sys.stdin.readline().rstrip()
 
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = 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)

n,m=list(map(int,input().split()))
EE=[]
if m<3:
  print(-1)
else:
  edge = [[] for i in range(n)]
  a,b=list(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=list(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 array
import math
import os
import random
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()

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

n,m=map(int,input().split())
maxi=1000009
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])
    #print(a[i])
for i in range(1,n+1):
    if a[i] not in d:
        d[a[i]]=count
        count+=1
#print(d)  
if len(d)!=3:
    #print(s)
    print("-1")
    return
for i in range(1,n+1):
    print(d[a[i]],end=" ")
  

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=" ")
  
    

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=" ")
  

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 list(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 = list(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
    1 2
    1 3
    1 4
    1 5
    1 6
    2 4
    2 5
    2 6
    3 4
    3 5
    3 6"""
        )
    )

    answer(
        string_source(
            """4 6
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4"""
        )
    )