萌萌交互题。
对网格图进行二分图建模，左部 \(n\) 个点表示每一行，右部 \(n\) 个点表示每一列。若格子 \((i,j)\) 被染成 \(c\) 色，就连接 \((L_i,R_j,c)\) 的边。
由抽屉原理易证，在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不同的四元环。
讨论环长是否为四的倍数。若不为四的倍数，则询问任意一对正对面的点对应的格子；若为四的倍数，错开一位即可。（如图所示）
这样，我们就可以将大环划分为两个大小约为一半的小环。显然，无论询问的边被染成什么颜色，两个小环之中至少有一个不包含这种颜色。在第一个图中为左半部分，在第二个图中为右半部分。
至此，我们可以由一个各边颜色均不同的偶环，经过一次询问，得到一个规模减半的各边颜色依然不同的偶环。重复询问直到环长为四，最大询问次数不超过 \(10\)。
需要注意的一点是，在每组数据结束后，需要读入一行字符串 OK。
// Problem: Good Colorings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1887E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const int N = 2e3 + 5;
int T, n, col[N][N], vis[N];
vector<int> e[N], cyc;
stack<int> stk;
bool dfs(int u, int f) {
vis[u] = 1;
stk.push(u);
for(int v : e[u]) {
if(v == f || vis[v] == 2) continue;
if(vis[v] == 1) {
if(v <= n) cyc.push_back(v);
while(stk.top() != v) {
cyc.push_back(stk.top());
stk.pop();
}
if(v > n) cyc.push_back(v);
return true;
}
if(dfs(v, u)) return true;
}
vis[u] = 2;
stk.pop();
return false;
}
void solve() {
cin >> n;
rep(i, 1, 2 * n) {
int u, v;
cin >> u >> v;
e[u].push_back(n + v);
e[n + v].push_back(u);
col[u][n + v] = i;
col[n + v][u] = i;
}
rep(i, 1, 2 * n) if(vis[i] == 0) if(dfs(i, 0)) break;
while(cyc.size() > 4) {
int sz = cyc.size();
int uid = 0, vid = sz % 4 == 0 ? sz / 2 + 1 : sz / 2;
int u = cyc[uid], v = cyc[vid], c;
cout << "? " << u << " " << v - n << endl << flush;
cin >> c;
col[u][v] = col[v][u] = c;
bool flag = true;
rep(i, uid, vid - 1) if(col[cyc[i]][cyc[i + 1]] == c) flag = false;
vector<int> tmp;
if(flag) {
rep(i, uid, vid) tmp.push_back(cyc[i]);
}
else {
tmp.push_back(cyc[uid]);
per(i, cyc.size() - 1, vid) tmp.push_back(cyc[i]);
}
swap(cyc, tmp);
}
cout << "! " << cyc[0] << " " << cyc[2] << " " << cyc[1] - n << " " << cyc[3] - n << endl << flush;
string result;
cin >> result;
assert(result == "OK");
}
void clear() {
rep(i, 1, 2 * n) {
rep(j, 1, 2 * n) col[i][j] = 0;
vis[i] = 0;
e[i].clear();
}
cyc.clear();
while(!stk.empty()) stk.pop();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(cin >> T; T; --T) {
solve();
clear();
}
return 0;
}