#include "highway.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe ll t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l,ll r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf = 4e18+1;
const ll mod2 = 1e9+7;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
ll kk;
ll el = 19;
ll cost[2];
struct ib
{
ll a,b;
};
vector<ib> ke[90001],a;
vector<int> v;
ll go[90001],floy,dia;
ll dist[90001];
bool check[130001];
void bfs(ll x)
{
deque<ib> q;
memset(go,-1,sizeof go);
q.push_front({0,x});
while(!q.empty())
{
ib x=q.front();
q.pop_front();
if(go[x.b]!=-1) continue;
go[x.b]=x.a;
for(auto f:ke[x.b])
if(!check[f.b])
q.pb({x.a+1,f.a});
}
}
bool cmpp(ib a,ib b)
{
return a.a>b.a;
}
ll dnc(vector<ib>a)
{
if(a.size()==0) assert(0);
if(a.size()==1) return a[0].a;
ll mid=a.size()/2;
vector<ib> cd;
vector<int>haha=v;
for(ll i=0; i<mid; i++)
for(auto x:ke[a[i].a])
haha[x.b]=1;
if(ask(haha)==floy)for(ll i=mid; i<a.size(); i++)cd.pb(a[i]);
else for(ll i=0; i<mid; i++)cd.pb(a[i]);
return dnc(cd);
}
void find_pair(int N,vector<int> U,vector<int> V,int A,int B)
{
n=N;
m=U.size();
ll min_cost=A;
ll max_cost=B;
for(ll i=0; i<m; i++)
ke[U[i]].pb({V[i],i}),
ke[V[i]].pb({U[i],i});
for(ll i=0; i<m; i++)v.pb(0);
floy=ask(v);
dia=floy/A;
l=0;
r=m-2;
while(l<=r)
{
ll mid=l+r>>1;
for(ll i=0; i<=mid; i++)
v[i]=1;
if(ask(v)!=floy)r=mid-1;
else l=mid+1;
for(ll i=0; i<=mid; i++)
v[i]=0;
}
r++;
for(ll i=0; i<r; i++)
check[i]=1;
for(ll i=0; i<r; i++)
v[i]=1;
bfs(U[r]);
for(ll i=0; i<n; i++)
if(go[i]!=-1)
a.pb({go[i],i});
root=r;
sort(a.begin(),a.end(),cmpp);
l=0;
r=a.size()-2;
while(l<=r)
{
ll mid=l+r>>1;
vector<int> hihi=v;
for(ll i=0; i<=mid; i++)
for(auto x:ke[a[i].b])
hihi[x.b]=1;
if(ask(hihi)!=floy)r=mid-1;
else l=mid+1;
}
ll pos1=a[r+1].b;
for(ll i=0; i<n; i++)
dist[i]=go[i];
bfs(a[r+1].b);
a.clear();
for(ll i=0; i<n; i++)
if(go[i]==dia)
a.pb({i,i});
ll pos2;
pos2=dnc(a);
answer(pos1,pos2);
}
