Building Teams

# idea is to use bipartite check. All nodes will have either red or blue colour, denoted by 0 or 1 value. If there are 2 adjacent nodes that have the same colour, means cannot split the pupils into 2 groups so no valid solution

# bipartite check
# every node should have a colour or value, 0 or 1
# do bfs to visit each node, colour them accordingly, check for same colours
# record the neighbours of every pupil so that you can repeat bfs

from collections import deque

n, m = map(int, input().split())
colourList = [-1] * n
pupilFriendList = [[] for i in range(n)]

for i in range(m):
  friend1, friend2 = map(int, input().split())
  pupilFriendList[friend1 - 1].append(friend2 - 1)
  pupilFriendList[friend2 - 1].append(friend1 - 1)

# bfs will colour neighbours accordingly and check for same colour and return true or false whether solution valid or not
def bfs(i):
  # using queue
  q = deque([i])

  while q:
    node = q.popleft()
    neighbours = pupilFriendList[node]

    for neighbour in neighbours:
      if colourList[node] == colourList[neighbour]:
        # no possible solution
        return False
      # not coloured yet
      elif colourList[neighbour] == -1:
        # so that always alternate 0 or 1
        colourList[neighbour] = 1 - colourList[node]
        q.append(neighbour)

  # if iterate through whole graph using bfs and no issues, then return True because groups can be formed from this graph
  return True

flag = True

# iterate through every pupil to colour, do bfs and check for same colours
for i in range(n):
  # -1 means not visited yet and also means first node
  if colourList[i] == -1:
    # mark it as first node and colour with value 1
    colourList[i] = 1
    # if no valid solution because this means no groups can be formed and totally no solution
    if not bfs(i):
      flag = False
      print("IMPOSSIBLE")
      break

if flag:
  # print groups
  for colour in colourList:
    print(colour + 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: 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