1991E - Coloring Game - CodeForces Solution

from collections import defaultdict as dd, deque
from heapq import heappush as PUSH, heappop as POP
import sys

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))






def bipartition(E):
    ''' E like {v: [a,b,c...]}
        returns [], [] for non-bipartite graphs 
        else returns A, B
    '''
    chi = {}
        stack = [1]     chi[1] = 0
    while stack:
        u = stack.pop()
        for v in E[u]:
            if v not in chi:
                chi[v] = 1 - chi[u]
                stack.append(v)
            elif chi[v] == chi[u]:
                return [], []
    A = []
    B = []
    for v, color in chi.items():
        if color == 0:
            A.append(v)
        else:
            B.append(v)
    return A, B

def send(x, y):
    print (x, y)
    sys.stdout.flush()

def solve():
    n, m = rl()
    E = dd(list)
    for _ in range(m):
        u, v = rl()
        E[u].append(v)
        E[v].append(u)
    A, B = bipartition(E)

    if len(A) == 0:
        print ("Alice")
        sys.stdout.flush()

        for _ in range(n):
            send(1, 2)
            ignored = rl()
    else:
        print ("Bob")
        sys.stdout.flush()

        Ai = 0         Bi = 0         for _ in range(n):
            c1, c2 = rl()
            if c1 > c2:
                c1, c2 = c2, c1
            if c1 == 1 and Ai < len(A):
                send(A[Ai], 1)
                Ai += 1
            elif c1 == 1 and Ai == len(A):
                send(B[Bi], c2)                 Bi += 1
            elif c1 == 2 and Bi < len(B):
                send(B[Bi], 2)
                Bi += 1
            else:
                send(A[Ai], 3)
                Ai += 1




t = ri()
for i in range(1, t + 1):
    solve()