Building Teams

# import sys
# from collections import deque

# def solve_teams():
#     input_data = sys.stdin.read().split()
#     if not input_data:
#         return

#     n = int(input_data[0])
#     m = int(input_data[1])

#     graph = {i: [] for i in range(1, n + 1)}
#     idx = 2
#     for _ in range(m):
#         u = int(input_data[idx])
#         v = int(input_data[idx+1])
#         graph[u].append(v)
#         graph[v].append(u)
#         idx += 2
# #initially 0 then assigned
#     team_assignment = [0] * (n + 1)

#     for pupil in range(1, n + 1):
#         if team_assignment[pupil] == 0:
#             team_assignment[pupil] = 1
#             queue = deque([pupil])

#             while queue:
#                 current = queue.popleft()
#                 current_team = team_assignment[current]
#                 #friend in ooposite
#                 opposite_team = 2 if current_team == 1 else 1

#                 for friend in graph[current]:
#                     if team_assignment[friend] == 0:
#                         team_assignment[friend] = opposite_team
#                         queue.append(friend)
#                     elif team_assignment[friend] == current_team:
#                         print("IMPOSSIBLE")
#                         return

#     team_1 = [str(i) for i in range(1, n + 1) if team_assignment[i] == 1]
#     team_2 = [str(i) for i in range(1, n + 1) if team_assignment[i] == 2]

#     # print(f"Team 1: {', '.join(team_1)}")
#     # print(f"Team 2: {', '.join(team_2)}")
#     print(pupil.team_assignment())

# if __name__ == "__main__":
#     solve_teams()



import sys
from collections import deque

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    iterator = iter(input_data)
    
    try:
        n_str = next(iterator)
    except StopIteration:
        return
        
    n = int(n_str)
    m = int(next(iterator))
    
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(iterator))
        v = int(next(iterator))
        graph[u].append(v)
        graph[v].append(u)

    teams = [0] * (n + 1)
    
    for pupil in range(1, n + 1):
        if teams[pupil] == 0:
            teams[pupil] = 1
            queue = deque([pupil])
            
            while queue:
                curr = queue.popleft()
                curr_team = teams[curr]
#alternate teams
                neighbor_team = 2 if curr_team == 1 else 1
                
                for friend in graph[curr]:
                    if teams[friend] == 0:
                        teams[friend] = neighbor_team
                        queue.append(friend)
                    elif teams[friend] == curr_team:
                        #if a&b and a&c but b&c can't be so
                        print("IMPOSSIBLE")
                        return
                        

    sys.stdout.write(" ".join(str(teams[i]) for i in range(1, n + 1)) + "\n")

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