[백준,PS,그래프탐색][PYTHON] #13265. 색칠하기

from collections import deque


def bfs(x):#색칠비교 + BFS
    global stop
    q.append(x)#큐에넣어주고
    visited[x] =1#방문한 초기설정
    color[x] = 1 #색깔이 1이라고 가정 다음 인접한 노드들은 색깔들이 2여야한다.
    
    while q:
        x = q.popleft() # 한가지를 pop하고
        
        for i in range(len(a[x])): #반복문이 도는 이유는 인접한 모든 노드들에관하여야 하기때문에
            w = a[x][i] #i번째 인접노드
            if ( visited[w] == 0 ): #방문을 아직 하지않은노드라면? - >방문하고 색깔을 바꿔야한다.ex이전이 1이었으면 다음은 2 2였으면 다음은 1
                visited[w] = 1#방문함을 알리고
                if ( color[x] == 1):#현재 색깔이 1이라면
                    color[w]= 2#다음은 2가되어야함
                else:#현재 색깔이 2라면
                    color[w] =1#다음은 1이되어야함
                q.append(w) #다했다면 인접노드들을 다시 큐에 추가시켜야한다.
            
            
            if (visited[w] ==1  and color[x] ==color[w]): #내가 방문한 전노드랑 색깔이 같을때
                
                stop +=1 #플래그를 위해서
                
                return -1
                
test_case = int(input())

for  _ in range(test_case):
    
    vertex , edge = map(int, input().split())
    a =[ [] for _ in range(vertex+1)]
    color =[ 0 for _ in range(vertex+1)]#+1해준것은 1번노드 그래프가 0번 인덱스 보다는 1번인덱스에 저장되게 하기위해서
    visited= [0 for _ in range(vertex+1)]
    stop =0
    q = deque() #deque 라이브러리
    for i in range(edge):
        x,y = map(int, input().split())
        a[x].append(y)
        a[y].append(x)#교차되는것은 쌍방이기때문에
        
    
    bfs(1)
    
    for i in range(len(color)): #input case 중에서 끊어진 그래프가 나올수 있기 때문에  그렇다면 bfs시작점을 한번더 추가시켜야되기 때문이다.
        if color[i] ==0:# BFS가 한번에 전부다 이루어 져야한다는 편견을 버리자.
            bfs(i)

    if(stop ==0): #stop 플래그 설정
        print("possible")
    else:
        print("impossible")