Building Teams

import sys
sys.setrecursionlimit(1000000000)
n = input().split(" ")
m = int(n[1])
n = int(n[0])

connect = []
visited = [-1]
adj = [[]]
x = 0

for i in range(n):
    visited.append(0)
    adj.append([])

for i in range(m):
    f = input().split(" ")
    f = [int(f[0]), int(f[1])]

    adj[f[0]].append(f[1])
    adj[f[1]].append(f[0])


def dfs(s, t):
    if visited[s] != 0:
        if visited[s] == t:
            global x
            x = 1
        return
    visited[s] = t%2 + 1
    for c in adj[s]:
        dfs(c, t%2 + 1)

for i, p in enumerate(visited):
    if p == 0:
        dfs(i, 1)

if x == 1:
    print("IMPOSSIBLE")
else:
    for i in visited[1:-1]:
        print(i, end=" ")
    print(visited[-1])

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