#include<bits/stdc++.h>
#include "highway.h"
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
vector<pii> v[maxn];
vector<int> vert, ids;
int h[maxn], par[maxn], parid[maxn];
ll len;
int A, B;
int ask2(vector<int> vec){
ll num = ask(vec);
return (num - len) / (B-A);
}
void fill(int u, int pr){
vert.PB(u);
for(auto [y, c] : v[u])
if(y != pr){
h[y] = h[u] + 1;
par[y] = u;
parid[y] = c;
ids.PB(c);
fill(y, u);
}
}
bool mark[maxn];
int solve(int m, int rt, int pr){
vert.clear();
ids.clear();
h[rt] = 0;
fill(rt, pr);
vector<int> vec(m);
for(int id : ids)
vec[id] = 1;
int H = ask2(vec);
vector<int> lfs;
for(int x : vert){
if(h[x] == H){
lfs.PB(x);
}
}
int l = 0, r = sz(lfs);
while(r-l > 1){
int mid = (l+r) >> 1;
memset(mark, 0, sizeof mark);
fill(vec.begin(), vec.end(), 0);
mark[rt] = 1;
for(int i = l; i < mid; i++){
int tmp = lfs[i];
while(!mark[tmp]){
vec[parid[tmp]] = 1;
tmp = par[tmp];
}
}
if(ask2(vec) == H)
r = mid;
else
l = mid;
}
return lfs[l];
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
::A = A, ::B = B;
int m = sz(U);
for(int i = 0; i < m; i++){
v[U[i]].PB({V[i], i});
v[V[i]].PB({U[i], i});
}
vector<int> vec(m);
for(int &x : vec)
x = 0;
len = ask(vec);
int l = 0, r = m;
while(r-l > 1){
int mid = (l+r) >> 1;
for(int i = 0; i < m; i++)
vec[i] = 0;
for(int i = l; i < mid; i++)
vec[i] = 1;
if(ask(vec) > len)
r = mid;
else
l = mid;
}
answer(solve(m, U[l], V[l]), solve(m, V[l], U[l]));
}
