Building Teams

n, m = map(int, input().split())
team = []
e = []
for i in range(n):
    team.append(-1)
    e.append([])
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    e[a].append(b)
    e[b].append(a)

visited = [False for _ in range(n)]
visited_count = 0
nextt = 0
while visited_count < n:
    work = [nextt]
    team[nextt] = 0
    while len(work) > 0:
        cur = work.pop(0)
        visited[cur] = True
        visited_count += 1
        cur_team = team[cur]
        for friend in e[cur]:
            if not visited[friend]:
                team[friend] = not cur_team
                work.append(friend)
            else:
                if team[friend] == cur_team:
                    print("IMPOSSIBLE")
                    exit(0)
    while nextt < n and visited[nextt]:
        nextt += 1
    

for i in range(n):
    print(f"{team[i] + 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