#include "highway.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
vector<pair<int,int>>adj[90005];
vector<int>nodes[90005];
vector<int>edges[90005];
int paredge[200005];
int m;
long long ask(const std::vector<int> &w);
void answer(int s, int t);
long long querybottom(int st,int dr)
{
vector<int>query;
for(int i=0;i<m;i++)
{
query.push_back(0);
}
for(int i=st;i<=dr;i++)
{
for(auto j:edges[i])
{
query[j]=1;
}
}
return ask(query);
}
long long querylayer(int layer,int st,int dr)
{
vector<int>query;
for(int i=0;i<m;i++)
{
query.push_back(0);
}
for(int i=st;i<=dr;i++)
{
query[paredge[nodes[layer][i]]]=1;
}
return ask(query);
}
void dfs(int curr,int par,int dept)
{
for(auto k:adj[curr])
{
if(k.first!=par)
{
nodes[dept+1].push_back(k.first);
edges[dept+1].push_back(k.second);
paredge[k.first]=k.second;
dfs(k.first,curr,dept+1);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
m = U.size();
for(int i=0;i<U.size();i++)
{
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
for(int i=0;i<N;i++)
{
nodes[i].clear();
}
long long dist=querybottom(N,N);
//cout<<dist<<'\n';
nodes[0].push_back(0);
dfs(0,-1,0);
int dr=N,st=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(querybottom(mij,N)!=dist)
{
st=mij+1;
}
else
{
dr=mij-1;
}
}
int botlayer=st-1;
//cout<<"botlayer"<<botlayer<<'\n';
st=0,dr=nodes[botlayer].size()-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(querylayer(botlayer,0,mij)!=dist)
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
//cout<<"firstnode"<<" "<<nodes[botlayer][dr+1]<<'\n';
int root=nodes[botlayer][dr+1];
for(int i=0;i<N;i++)
{
nodes[i].clear();
edges[i].clear();
}
dfs(root,-1,0);
botlayer=dist/A;
st=0,dr=nodes[botlayer].size()-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(querylayer(botlayer,0,mij)!=dist)
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
int second=nodes[botlayer][dr+1];
for(int i=0;i<N;i++)
{
nodes[i].clear();
edges[i].clear();
adj[i].clear();
}
answer(root, second);
}
