Here is my code for 1991E - Coloring Game. I am getting memory limit exceeded on test case 2. Strange. I am doing bfs first then simply intracting with the judger.
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)
