[백준/BOJ] - 13265번 python 풀이 - bfs

import sys
from collections import deque

def bfs(x):
    queue = deque([x])    
    color[x] = 1 #맨 처음 값 1로 칠하기
    point = 2 #컬러 변수

    while queue:
        v = queue.popleft()  
        if color[v] == 1:
            point = 2
        else:
            point = 1
        for i in graph[v]:
            if color[i] == 0: #방문 안했다면
                color[i] = point #point로 색칠
                queue.append(i)
            else: #방문 했다면
                if color[v] == color[i]: #색이 같아 버리면
                    return True

T = int(input())

for i in range(T):
    n,m = map(int,input().split()) #노드, 선
    graph = [[] for _ in range(n+1)]
    color = [0 for _ in range(n+1)]
    for j in range(m):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    for k in range(1,n+1):
        if color[k] == 0: #방문 안한 노드
            if bfs(k) == True:
                print("impossible")
                break
            else:
                print("possible")