Building Teams

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

teams = [0] * (n+1)
reps = []

def dfs(start):
    stack = [start]
    teams[start] = 0
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if teams[v] == 0:
                teams[v] = 1 - teams[u]
                stack.append(v)
            elif teams[v] == teams[u]:
                print("IMPOSSIBLE")
                exit()

# connected components
for i in range(1, n+1):
    if teams[i] == 0:
        reps.append(i)
        dfs(i)

result = []
for i in range(1, n+1):
    result.append(teams[i] + 1)

print(*result)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED