#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
long long ask(const std::vector<int> &w);
void answer(int s, int t);
const ll NP=1e5;
vector<pair<ll,ll>> ma[NP],tmp;
vector<int> w;
ll mi,a,b,par[NP],vis[NP];
ll wantd;
vector<int> ans;
void dfs(int x,int p=-1,ll d=0)
{
par[x]=p;
if(d==(wantd))
ans.pb(x);
for(auto y:ma[x])
{
if(y.second!=p)
{
dfs(y.second,x,d+1);
}
}
}
map<pair<int,int>,int> edg;
// vector<int> path,node;
// void dfs_(int x,int p=-1)
// {
// node.pb(x);
// for(auto [id,y]:ma[x])
// {
// if(y!=p)
// {
// path.push_back(id);
// dfs_(y,x);
// }
// }
// }
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B)
{
bool subtask=1;
int m=u.size();
w.resize(m,0);
a=A;
b=B;
mi=ask(w);
// cout<<"For w: ";
// for(auto j:w)
// cout<<j<<' ';
// cout<<endl;
// cout<<"answer "<<mi<<endl;
wantd=(mi/a);
for(int i=0;i<n;i++)
ma[i].clear();
for(int i=0;i<m;i++)
{
edg[{u[i],v[i]}]=i;
edg[{v[i],u[i]}]=i;
ma[u[i]].pb({i,v[i]});
ma[v[i]].pb({i,u[i]});
}
for(int i=0;i<m;i++)
{
if(u[i]==i and v[i]==(i+1))
{
}
else{
subtask=0;
}
}
if(subtask)
{
int s=-1;
int e=n;
while(s+1<e)
{
int mid=(s+e)/2;
for(int j=0;j<=mid;j++)
{
w[j]=1;
}
ll wa=ask(w);
// cout<<"Check S "<<mid<<endl;
// cout<<"For w: ";
// for(auto j:w)
// cout<<j<<' ';
// cout<<endl;
// cout<<"answer "<<wa<<endl;
for(int j=0;j<=mid;j++)
{
w[j]=0;
}
if(wa==mi)
{
s=mid;
// no edge
}
else
{
e=mid;
}
}
int str=s;
s=-1;
e=n;
while(s+1<e)
{
int mid=(s+e)/2;
for(int j=n-1;j>=mid;j--)
{
w[j]=1;
}
ll wa=ask(w);
// cout<<"Check E "<<mid<<endl;
// cout<<"For w: ";
// for(auto j:w)
// cout<<j<<' ';
// cout<<endl;
// cout<<"answer "<<wa<<endl;
for(int j=n-1;j>=mid;j--)
{
w[j]=0;
}
if(wa==mi)
{
e=mid;
// no edge
}
else
{
s=mid;
}
}
// cout<<"Check\n";
// cout<<str+1<<' '<<e<<endl;
answer(str+1,e);
}
else
{
dfs(0);
int s=-1;
int e=ans.size();
while(s+1<e)
{
int mid=(s+e)/2;
for(int i=0;i<n;i++)
vis[i]=0;
vector<int> cur;
for(int j=s+1;j<=mid;j++)
{
int s=ans[j];
while(s!=0)
{
if(vis[s])break;
vis[s]=1;
cur.push_back(edg[{s,par[s]}]);
s=par[s];
}
}
for(auto i:cur)
w[i]=1;
ll wa=ask(w);
for(auto i:cur)
w[i]=0;
if(wa==(b*wantd))
{
e=mid;
}
else
{
s=mid;
}
}
answer(0,ans[e]);
}
}
