Building Teams

import sys
from collections import deque

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    n, m = int(input_data[0]), int(input_data[1])
    
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v = int(input_data[2 + 2*i]), int(input_data[3 + 2*i])
        adj[u].append(v)
        adj[v].append(u)
        
    team = [0] * (n + 1)
    
    for i in range(1, n + 1):
        if team[i] == 0:
            team[i] = 1
            q = deque([i])
            
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if team[v] == 0:
                        team[v] = 3 - team[u]
                        q.append(v)
                    elif team[v] == team[u]:
                        print("IMPOSSIBLE")
                        return
                        
    print(" ".join(map(str, team[1:])))

if __name__ == '__main__':
    solve()

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