#include "highway.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> depth;
vector<pair<int,int>> parent;
vector<int> sz;
vector<vector<pair<int,int>>> child;
vector<vector<pair<int,int>>> neigh;
vector<vector<pair<int,int>>> neigh2;
vector<signed> aska;
int S=-1;
int M,N;
int shortest;
int totCount=0;
int prevP=0;
int getSIZE(int x){
sz[x]=1;
for (auto u : child[x])
{
sz[x]+=getSIZE(u.first);
}
return sz[x];
}
int find_centroid(int _x){
int x = _x;
int sizeT=sz[_x];
while (true) {
int c = -1;
for (int i = 0; i < sz(child[x]); i++) {
if (sz[child[x][i].first]>sizeT/2) c = child[x][i].first;
}
//if (sz[x]-1>sizeT/2&&parent[x].first!=-1) c = parent[x].first;
if (c!=-1) x = c;
else break;
}
return x;
}
void reroot(int R){
child.clear();
parent.clear();
child.resize(N);
parent.resize(N);
queue<pair<int,int>> q;
q.push({R,-1});
parent[R]={-1,-1};
while(!q.empty()){
int x=q.front().first,p=q.front().second; q.pop();
for (auto u : neigh2[x])
{
if(u.first==p||u.first==-1) continue;
child[x].push_back(u);
parent[u.first]={x,u.second};
q.push({u.first,x});
}
}
}
void colorSubtree(int x){
aska[parent[x].second]=1;
for (auto u : child[x])
{
colorSubtree(u.first);
}
}
int findTree(int x){
int l=0, r=sz(child[x])-1;
aska.resize(M);
int ans=-1;
while(l<=r){
for (int i = 0; i < M; i++) aska[i]=0;
int mid=(l+r)/2;
for (int i = 0; i <= mid; i++)
{
colorSubtree(child[x][i].first);
}
totCount++;
if(ask(aska)>shortest){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans<0) {
for (int i = 0; i < M; i++) aska[i]=0;
if(parent[x].first>-1) {
aska[parent[x].second]=1;
if(ask(aska)>shortest){
S=x;
return S;
}
for (int i = 0; i < sz(neigh2[parent[x].first]); i++)
{
if(neigh2[parent[x].first][i].first==x){
neigh2[parent[x].first][i].first=-1;
}
}
return prevP;
}
S=x;
return S;
}
else{
for (int i = 0; i < sz(neigh2[child[x][ans].first]); i++)
{
if(neigh2[child[x][ans].first][i].first==x){
neigh2[child[x][ans].first][i].first=-1;
}
}
return child[x][ans].first;
}
}
void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B){
M=sz(U);
N=n;
neigh.resize(N);
neigh2.resize(N);
child.resize(N);
sz.resize(N);
depth.resize(N);
parent.resize(N);
vector<signed> ep(M,0);
shortest=ask(ep);
int initDist=shortest/A;
totCount=0;
for (int i = 0; i < M; i++)
{
neigh[U[i]].push_back({V[i],i});
neigh[V[i]].push_back({U[i],i});
neigh2[U[i]].push_back({V[i],i});
neigh2[V[i]].push_back({U[i],i});
}
int c=0;
reroot(0);
while(S<0){
//cerr<<c<<"\n";
prevP=c;
getSIZE(c);
int _c=find_centroid(c);
_c=findTree(_c);
c=_c;
reroot(c);
if(sz(child[c])==0) {
S=c;
}
}
vector<int> possible;
queue<pair<int,int>> q;
q.push({S,-1});
child.clear();
parent.clear();
depth.clear();
neigh.resize(N);
child.resize(N);
depth.resize(N);
parent.resize(N);
depth[S]=0;
while(!q.empty()){
int x=q.front().first,p=q.front().second; q.pop();
if(depth[x]==initDist) possible.push_back(x);
for (auto u : neigh[x])
{
if(u.first==p) continue;
child[x].push_back(u);
depth[u.first]=depth[x]+1;
parent[u.first]={x,u.second};
q.push({u.first,x});
}
}
int l=0; int r=sz(possible)-1;
while(l<r){
int mid=(l+r)/2;
vector<signed> w(M,0);
for (int i = l; i <= mid; i++) { w[parent[possible[i]].second]=1; }
if(ask(w)>shortest){
r=mid;
}else{
l=mid+1;
}
}
answer(S,(int)possible[l]);
}
