Building Teams

n, m = map(int, input().split())
team = {i + 1: -1 for i in range(n)}
e = {}
for i in range(m):
    a, b = map(int, input().split())
    if a not in e:
        e[a] = set()
    if b not in e:
        e[b] = set()
    e[a].add(b)
    e[b].add(a)

visited = set()
unvisited = 1
while len(visited) < n:
    work = [unvisited]
    team[unvisited] = 0
    while len(work) > 0:
        cur = work.pop(0)
        visited.add(cur)
        cur_team = team[cur]
        for friend in e[cur]:
            if friend not in visited:
                team[friend] = 1 - cur_team
                work.append(friend)
            else:
                if team[friend] == cur_team:
                    print("IMPOSSIBLE")
                    exit(0)
    while unvisited in visited:
        unvisited += 1
    

for i in range(n):
    print(f"{team[i + 1] + 1} ", end="")
print()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED