#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;
vector<vector<pi> > a(N);
vector<pi> pos;
vector<pi> par(N);
void dfs(int s, int e, int cur, int f){
if(cur == f){
pos.push_back({par[s].S,s});
return;
}
for(auto x : a[s]){
if(x.F == e)continue;
par[x.F] = {s,x.S};
dfs(x.F,s,cur+1,f);
}
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
int i;
int m = u.size();
for(i=0;i<m;i++){
a[v[i]].push_back({u[i],i});
a[u[i]].push_back({v[i],i});
}
vector<int> w(m,0);
ll d = ask(w);
int dep = d/A;
dfs(0,0,0,dep);
assert(pos.size() > 0);
int l = 0,r = pos.size() - 1;
while(l < r){
int mid = (l+r)/2;
for(i=0;i<=mid;i++){
w[pos[i].F] = 1;
}
ll res = ask(w);
for(i=0;i<=mid;i++){
w[pos[i].F] = 0;
}
if(res != d){
r = mid;
}
else{
l = mid+1;
}
}
answer(0,pos[r].S);
}
