Coloring Game

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n);
 
	// Armamos el grafo
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[--u].push_back(--v);
		adj[v].push_back(u);
	}
 
	vector<int> c(n, -1);
	c[0] = 0;
 
	bool notBipartite = false;
	auto dfs = [&](auto &&self, int nd) -> void {
		for (int x : adj[nd]) {
			if (c[x] == -1) {
				c[x] = !c[nd];
				self(self, x);
			} else if (c[x] == c[nd]) {
				notBipartite = true;
				return;
			}
		}
	};
 
	// DFS para chequear si el grafo es bipartito
	dfs(dfs, 0);
 
	if (notBipartite) {
		// Si no es bipartito, gana Alice
		int gb;
		cout << "Alice" << endl;
		for (int i = 0; i < n; i++) {
			cout << 1 << " " << 2 << endl;
			cin >> gb >> gb;
		}
	} else {
		// El grafo es bipartito, gana Bob
		cout << "Bob" << endl;
		array<vector<int>, 2> g;
		for (int i = 0; i < n; i++) { g[c[i]].push_back(i); }
 
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			if (a > b) { swap(a, b); }
			if (g[a].size()) {
				cout << g[a].back() + 1 << " " << a + 1 << endl;
				g[a].pop_back();
			} else {
				cout << g[!a].back() + 1 << " " << b + 1 << endl;
				g[!a].pop_back();
			}
		}
	}
}
 
int main() {
	int t;
	cin >> t;
	while (t--) { solve(); }
}

import sys
 
 
def solve():
	data = sys.stdin
 
	n, m = map(int, data.readline().split())
 
	# Armamos el grafo
	adj = [[] for _ in range(n)]
	for _ in range(m):
		u, v = map(int, data.readline().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
 
	c = [-1] * n
	c[0] = 0
	not_bipartite = False
 
	# Determinamos si el grafo es bipartito
	stack = [0]
	while stack and not not_bipartite:
		nd = stack.pop()
		for x in adj[nd]:
			if c[x] == -1:
				c[x] = c[nd] ^ 1
				stack.append(x)
			elif c[x] == c[nd]:
				not_bipartite = True
				break
 
	if not_bipartite:
		# Si no es bipartito, gana Alice
		print("Alice", flush=True)
		for _ in range(n):
			print(1, 2, flush=True)
			data.readline()
	else:
		# Si es bipartito, gana Bob
		print("Bob", flush=True)
		g = [[], []]
		for i in range(n):
			g[c[i]].append(i)
 
		for _ in range(n):
			a, b = map(int, data.readline().split())
			a -= 1
			b -= 1
			if a > b:
				a, b = b, a
 
			if g[a]:
				v = g[a].pop()
				print(v + 1, a + 1, flush=True)
			else:
				v = g[a ^ 1].pop()
				print(v + 1, b + 1, flush=True)
 
 
def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		solve()
 
 
if __name__ == "__main__":
	main()

 
import java.io.*;
import java.util.*;
 
public class ColoringGame {
	static List<Integer>[] adj;
	static int[] color;
	static boolean bad;
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 
		int t = Integer.parseInt(br.readLine().trim());
 
		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
 
			adj = new ArrayList[n];
			for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
 
			// Armamos el grafo
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken()) - 1;
				int v = Integer.parseInt(st.nextToken()) - 1;
				adj[u].add(v);
				adj[v].add(u);
			}
 
			color = new int[n];
			Arrays.fill(color, -1);
			color[0] = 0;
			bad = false;
 
			// Determinamos si el grafo es bipartito
			ArrayDeque<Integer> stack = new ArrayDeque<>();
			stack.push(0);
			while (!stack.isEmpty() && !bad) {
				int nd = stack.pop();
				for (int x : adj[nd]) {
					if (color[x] == -1) {
						color[x] = color[nd] ^ 1;
						stack.push(x);
					} else if (color[x] == color[nd]) {
						bad = true;
						break;
					}
				}
			}
 
			if (bad) {
				// Si el grafo no es bipartito, gana Alice
				out.println("Alice");
				out.flush();
 
				for (int i = 0; i < n; i++) {
					out.println("1 2");
					out.flush();
					br.readLine();
				}
			} else {
				// Si el grafo es bipartito, gana Bob
				out.println("Bob");
				out.flush();
 
				ArrayList<Integer>[] g = new ArrayList[2];
				g[0] = new ArrayList<>();
				g[1] = new ArrayList<>();
 
				for (int i = 0; i < n; i++) { g[color[i]].add(i); }
 
				for (int i = 0; i < n; i++) {
					st = new StringTokenizer(br.readLine());
					int a = Integer.parseInt(st.nextToken()) - 1;
					int b = Integer.parseInt(st.nextToken()) - 1;
					if (a > b) {
						int tmp = a;
						a = b;
						b = tmp;
					}
 
					if (!g[a].isEmpty()) {
						int v = g[a].remove(g[a].size() - 1);
						out.println((v + 1) + " " + (a + 1));
					} else {
						int v = g[a ^ 1].remove(g[a ^ 1].size() - 1);
						out.println((v + 1) + " " + (b + 1));
					}
					out.flush();
				}
			}
		}
 
		out.flush();
	}
}