Building Teams

import queue

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

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    # adj[b].append(a)

solution = [0] * (n + 1)
visited = set()
not_visited = set([i for i in range(1, n + 1)])
q = queue.Queue()


def dfs() -> bool:
    while not q.empty():
        node, team = q.get()

        if solution[node] == 0:
            solution[node] = team
        else:
            return False

        if node in visited:
            continue
        visited.add(node)
        not_visited.remove(node)
        for s in adj[node]:
            q.put((s, 1 if team == 2 else 2))
    return True


cycle = False
while len(visited) < n and not cycle:
    h = not_visited.pop()
    not_visited.add(h)
    q.put((h, 1))
    cycle = not dfs()

if cycle:
    print("IMPOSSIBLE")
else:
    print(" ".join(str(s) for s in solution[1:]))

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED