Here is my code for [problem:
↵
↵
~~~~~↵
import sys↵
input = sys.stdin.readline↵
↵
def solve(n , m, graph):↵
# print(graph)↵
ans = [set(), set()]↵
visited = [False] * (n + 1)↵
stack = [(1, 0, -1)]↵
alice_win = False↵
while stack and not alice_win:↵
new_stack = []↵
for num in stack:↵
visited[num[0]] = True↵
ans[num[1]].add(num[0])↵
for child in graph[num[0]]:↵
if child != num[2]:↵
if visited[child]:↵
if child in ans[num[1]]:↵
alice_win = True↵
break↵
else:↵
new_stack.append((child, (num[1] + 1) % 2, num[0]))↵
if alice_win:↵
break↵
↵
stack = new_stack↵
↵
↵
if alice_win:↵
print("Alice", flush=True)↵
sys.stdout.flush()↵
for i in range(n):↵
print(1, 2, flush=True)↵
sys.stdout.flush()↵
if input().strip() == "-1":↵
quit()↵
else:↵
print("Bob", flush=True)↵
sys.stdout.flush()↵
# print(ans)↵
ans[0] = list(ans[0])↵
ans[1] = list(ans[1])↵
if len(ans[0]) + len(ans[1]) != n:↵
raise Exception()↵
for i in range(n):↵
colors = input().strip()↵
if colors == "-1":↵
quit()↵
colors = list(map(int, colors.split()))↵
if len(ans[0]) == 0:↵
temp = ans[1].pop()↵
if 2 in colors:↵
print(temp, 2, flush=True)↵
elif 3 in colors:↵
print(temp, 3, flush=True)↵
sys.stdout.flush()↵
continue↵
if len(ans[1]) == 0:↵
temp = ans[0].pop()↵
if 1 in colors:↵
print(temp, 1, flush=True)↵
elif 3 in colors:↵
print(temp, 3, flush=True)↵
sys.stdout.flush()↵
continue↵
if 1 in colors:↵
temp = ans[0].pop()↵
print(temp, 1, flush=True)↵
sys.stdout.flush()↵
continue↵
if 2 in colors:↵
temp = ans[1].pop()↵
print(temp, 2, flush=True)↵
sys.stdout.flush()↵
continue↵
↵
↵
↵
↵
↵
def main():↵
for t in range(int(input())):↵
temp = input()↵
if temp == "-1":↵
quit()↵
n, m = map(int, temp.split())↵
graph = [[] for i in range(n + 1)]↵
for i in range(m):↵
a,b = map(int, input().split())↵
graph[a].append(b)↵
graph[b].append(a)↵
solve(n, m, graph)↵
~~~~~↵
↵
↵
