//#define local
#ifndef local
#include "highway.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
const ll N = 3e5 + 5;
const ll oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
ll rnd(ll l, ll r){
ll temp = rng() % (r - l + 1);
return abs(temp) + l;
}
// ask(vector<ll>)
vector<ii> Adj[N];
ll mini;
ll n, m;
vector<ii> v1, v2;
bool vis[N];
bool ck = 0;
vector<int> ok;
int dist;
/*
void dfs(ll u, ll d){
vis[u] = 1;
if(!ck) v1.pb({u, d});
else v2.pb({u, d});
// if(d == dist) ok.pb(u);
for(auto it : Adj[u]){
if(it.se < (mini - 1)) continue;
if(vis[it.fi]) continue;
dfs(it.fi, d + 1);
}
}*/
bool cmp(ii a, ii b){
return a.se > b.se;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n = N, m = U.size();
for(ll i = 0; i < m; i++){
Adj[U[i]].pb({V[i], i});
Adj[V[i]].pb({U[i], i});
}
// first step: find the optimal ans by toggle all 0s
ll opt;
vector<int> temp;
for(ll i = 0; i < m; i++) temp.pb(0);
opt = ask(temp);
// phase 1: let us set (1->i) to B in order to find a bridge + split graph llo two parts
ll le = 0, ri = m - 1;
while(le < ri){
ll mid = (le + ri) >> 1;
temp.clear();
for(ll i = 0; i <= mid; i++) temp.pb(1);
for(ll i = mid + 1; i < m; i++) temp.pb(0);
ll get = ask(temp);
if(get == opt) le = mid + 1;
else ri = mid;
}
mini = le + 1;
// phase 2: find S/T
ck = 0;
//dfs(U[le], 0);
queue<int> q;
vis[U[le]] = 1;
q.push(U[le]);
vector<int> distt(n + 1);
while(!q.empty()){
int u = q.front();
q.pop();
// if(distt[u] == dist) ok.pb(u);
v1.pb({u, distt[u]});
for(auto it : Adj[u]){
int v = it.fi;
if(it.se < (mini - 1)) continue;
if(!vis[v]){
vis[v] = 1;
distt[v] = distt[u] + 1;
q.push(v);
}
}
}
//ck = 1;
//dfs(V[le], 0);
sort(v1.begin(), v1.end(), cmp);
//sort(v2.begin(), v2.end(), cmp);
ll le2 = 0, ri2 = v1.size() - 1;
while(le2 < ri2){
ll mid = (le2 + ri2) >> 1;
temp.resize(m);
for(ll i = 0; i < le; i++) temp[i] = 1;
temp[le] = 0;
for(ll i = le + 1; i < m; i++) temp[i] = 0;
for(ll i = 0; i <= mid; i++){
ll u = v1[i].fi;
for(auto it : Adj[u]){
if(it.se < mini) continue;
temp[it.se] = 1;
}
}
ll get = ask(temp);
if(get == opt) le2 = mid + 1;
else ri2 = mid;
}
/*
ll le3 = 0, ri3 = v2.size() - 1;
while(le3 < ri3){
ll mid = (le3 + ri3) >> 1;
temp.resize(m);
for(ll i = 0; i < le; i++) temp[i] = 1;
temp[le] = 0;
for(ll i = le + 1; i < m; i++) temp[i] = 0;
for(ll i = 0; i <= mid; i++){
ll u = v2[i].fi;
for(auto it : Adj[u]){
if(it.se < mini) continue;
temp[it.se] = 1;
}
}
ll get = ask(temp);
if(get == opt) le3 = mid + 1;
else ri3 = mid;
}*/
int S = v1[(int)le2].fi;
dist = opt / A;
// cout << S << " " << opt << " " << A << " " << dist << "\n";
ok.clear();
mini = 0;
for(int i = 0; i < n; i++) vis[i] = 0;
for(int i = 0; i <= n; i++) distt[i] = 0;
vis[S] = 1;
q.push(S);
while(!q.empty()){
int u = q.front();
q.pop();
if(distt[u] == dist) ok.pb(u);
for(auto it : Adj[u]){
int v = it.fi;
if(!vis[v]){
vis[v] = 1;
distt[v] = distt[u] + 1;
q.push(v);
}
}
}
/// dfs(S, 0);
// for(auto it : ok) cout << it << " ";
// cout << "\n";
assert(ok.size());
int le3 = 0, ri3 = ok.size() - 1;
while(le3 < ri3){
int mid = (le3 + ri3) >> 1;
temp.resize(m);
for(int i = 0; i < m; i++) temp[i] = 0;
for(int i = 0; i <= mid; i++){
int u = ok[i];
for(auto it : Adj[u]) temp[it.se] = 1;
}
ll get = ask(temp);
if(get == opt) le3 = mid + 1;
else ri3 = mid;
}
int T = ok[le3];
answer(S, T);
//answer((int)v1[(int)le2].fi, (int)v2[(int)le3].fi);
}
#ifdef local
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while(t--) process();
}
#endif
