Building Teams

#input(n,m)
#input m lines of (a,b) friendship

#run through function (a,b)
#if a has been in lines with other bs
#    then go through bs, neighbors
#marked visited(a,b)
#put a in team 1, and put b in team 2 or 3
#if a not in friendship with, then put in same team.
#    circulate this algorithm until you have an idea of the team
#get the team number out
#otherwise print*impossible'



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

graph={i:[]for i in range(1,n+1)}
for _ in range(m):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited=set()
team={}

def dfs(node, current_team):
    visited.add(node)
    team[node]=current_team

    for neighbor in graph[node]:
        if neighbor not in visited:
            if not dfs(neighbor, 3-current_team):
                return False
        else:
            if team[neighbor]==current_team:
                return False
    return True

possible = True
for node in range(1, n+1):
    if node not in team:
        if not dfs(node, 1):
            possible = False
            break


print("impossible" if not possible else ' '.join(str(team[i]) for i in range(1, n+1)))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    if not...

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    if not...

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    if not...

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    if not...

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER