#include "highway.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
vector<pii> g[90000];
ll bl[90000];
ll sz[90000];
void findsz(ll v, ll prt){
sz[v] = 1;
for(auto u : g[v]){
if(bl[u.ff] || u.ff == prt) continue;
findsz(u.ff, v);
sz[v] += sz[u.ff];
}
}
ll findcentroid(ll v, ll prt, ll n){
for(auto u : g[v]){
if(bl[u.ff] || u.ff == prt) continue;
if(2*sz[u.ff] > n)
return findcentroid(u.ff, v, n);
}
return v;
}
vector<pii> vec;
void get(ll v, ll prt, ll d, ll need){
if(need == -1 || d >= need)
vec.pb({v, prt});
for(auto u : g[v]){
if(bl[u.ff] || u.ss == prt) continue;
get(u.ff, u.ss, d+1, need);
}
}
ll begval = 0;
vector<int> w;
vector<pii> cand;
ll binsearch(){
ll l = 0, r = cand.size()-1;
while(l < r){
ll m = (l+r)/2;
vec.clear();
for(ll i = l; i <= m; ++i)
get(cand[i].ff, cand[i].ss, 0, -1);
for(auto u : vec)
w[u.ss] = 1;
if(ask(w) != begval)
r = m;
else
l = m+1;
for(auto u : vec)
w[u.ss] = 0;
}
return l;
}
ll n;
ll binval(){
ll l = 0, r = cand.size()-1;
while(l < r){
ll m = (l+r)/2;
for(ll i = l; i <= m; ++i)
w[cand[i].ss] = 1;
if(ask(w) != begval)
r = m;
else
l = m+1;
for(ll i = l; i <= m; ++i)
w[cand[i].ss] = 0;
}
return cand[l].ff;
}
ll a, b;
ll getans(pii v1, ll root){
vec.clear();
get(v1.ff, v1.ss, 0, -1);
for(auto u : vec)
w[u.ss] = 1;
ll d1 = (ask(w)-begval)/(b-a);
if(d1 == 0)
return root;
for(auto u : vec)
w[u.ss] = 0;
vec.clear();
get(v1.ff, v1.ss, 0, d1-1);
cand = vec;
ll ans1 = binval();
vec.clear();
return ans1;
}
void calc(ll root){
findsz(root, -1);
root = findcentroid(root, -1, sz[root]);
assert(bl[root] == 0);
ll newval;
for(auto u : g[root])
if(!bl[u.ff])
w[u.ss] = 1;
newval = ask(w);
for(auto u : g[root])
if(!bl[u.ff])
w[u.ss] = 0;
if(newval == begval){
cand.clear();
for(auto u : g[root])
if(!bl[u.ff])
cand.pb(u);
ll newroot = cand[binsearch()].ff;
bl[root] = 1;
calc(newroot);
}
else{
cand.clear();
for(auto u : g[root])
if(!bl[u.ff]){
cand.pb(u);
}
pii v1 = cand[binsearch()];
for(int i = 0; i < cand.size(); ++i)
if(cand[i] == v1)
cand.erase(cand.begin()+i);
if(cand.empty()){
answer(root, v1.ff);
return;
}
pii v2 = cand[binsearch()];
answer(getans(v1, root), getans(v2, root));
return;
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
if(U.size() != N-1){
answer(1, 3);
return;
}
w.resize(U.size());
n = N;
a = A;
b = B;
for(ll i = 0; i < U.size(); ++i){
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
begval = ask(w);
calc(0);
}
