Участник:StasFomin/Solutions/codechef/QLK03

Ссылки сюда (1) →

• Codechef/QLK03

T = int(input())
for _ in range(T):
    N, K = list(map(int, input().strip().split())) 
    A = [[] for _ in range(N+1)]       # for every vertex we find its neighbours
    edges = []
    colors = dict()
    startnode = 1
 
    for _ in range(K):
        v, w = list(map(int, input().strip().split()))      #  1 <= v <= N,  1 <= w <= N
        edges.append((v, w))
        A[v].append(w)
        A[w].append(v)
 
    new_startnode = 2
    queue = [startnode]
    explored = 1
    current_color = 1
    colors[startnode] = current_color
 
    while explored < N:
        while len(queue) > 0:             #  queue is not empty
            v = queue[0]
            current_color = -colors[v]
 
            for w in A[v]:
                if colors.get(w) == None:
                    colors[w] = current_color
                    queue.append(w)
                    explored += 1
 
            queue.pop(0)
 
 
        if explored < N:
            while colors.get(new_startnode) != None:    
                new_startnode += 1
 
            startnode = new_startnode
            queue.append(startnode)
            explored += 1
            current_color = 1
            colors[startnode] = current_color
 
 
 
    answer = 'possible'
    for e in edges:
        v, w = e
        if colors[v] == colors[w]:
            answer = 'impossible'
            break
 
    print(answer)