很有意思的题。
考虑若无边权的限制则 B 必胜，不妨猜想有了限制之后仍然是 B 必胜。
假设 A 选了 I（若 A 选了 D 可以边权取相反数），若 B 走了 \((a,b)\)，A 走了 \((b,c)\)，则 B 还能走 \((c,d)\)。即 \(w_{b,c} > w_{a,b}\) 且 \(w_{b,c} < w_{c,d}\)，即不存在原图的匹配 \((a,b)\)，\((c,d)\) 使得 \(w_{a,b} < w_{b,c} < w_{c,d}\)。
将起点的一部（即 \(a,c\) 所在的一部）的所有点按照边权从大到小排序，另一部按照边权从小到大排序，则对于匹配 \((a,b)\)，\((c,d)\)，若 \(b\) 认为 \(c\) 比 \(a\) 优（\(w_{b,c} > w_{b,a}\)），则 \(c\) 不能认为 \(b\) 比 \(d\) 优（\(w_{c,b} < w_{c,d}\)）。这实际上就是稳定婚姻问题。由于稳定婚姻问题一定有解，因此原问题一定有解。
稳定婚姻问题算法流程：每轮一位单身男性表白之前没表白过的且最优的女性，若该女性无伴侣则他们结成伴侣；否则若该男性优于该女性伴侣，则该女性放弃之前的伴侣，与该男性结成伴侣。
code
// Problem: F. Zigzag Game
// Contest: Codeforces - Forethought Future Cup - Final Round (Onsite Finalists Only)
// URL: https://codeforces.com/problemset/problem/1147/F
// Memory Limit: 256 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
int n, a[maxn][maxn], b[maxn][maxn], c[maxn], pos[maxn];
vector<int> G[maxn];
void work(int op) {
queue<int> q;
mems(c, 0);
mems(pos, 0);
for (int i = 1; i <= n; ++i) {
q.push(i);
vector<int>().swap(G[i]);
for (int j = 1; j <= n; ++j) {
G[i].pb(j);
}
sort(G[i].begin(), G[i].end(), [&](int x, int y) {
return (a[i][x] < a[i][y]) ^ op;
});
}
for (int i = 1; i <= n; ++i) {
vector<int> vc;
for (int j = 1; j <= n; ++j) {
vc.pb(j);
}
sort(vc.begin(), vc.end(), [&](int x, int y) {
return (a[x][i] > a[y][i]) ^ op;
});
for (int j = 0; j < n; ++j) {
b[i][vc[j]] = j + 1;
}
}
while (q.size()) {
int u = q.front();
q.pop();
while (!c[u]) {
int v = G[u][pos[u]++];
if (!c[v + n] || b[v][u] < b[v][c[v + n]]) {
c[c[v + n]] = 0;
if (c[v + n]) {
q.push(c[v + n]);
}
c[u] = v + n;
c[v + n] = u;
}
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
}
}
puts("B");
fflush(stdout);
char op[9];
int x;
scanf("%s%d", op, &x);
if (op[0] == 'D') {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = -a[i][j];
}
}
}
work(x > n);
do {
printf("%d\n", c[x]);
fflush(stdout);
scanf("%d", &x);
if (x == -2) {
exit(0);
}
} while (x != -1);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}