#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ad push_back
#define MP make_pair
#define lli long long
#define fr first
#define sc second
const int N = 1e6 + 30;
int n, m;
vector<pair<int, int> > g[N], fp;
vector<int> w;
int xr[N], col[N];
pair<int, int> pr[N];
lli sum;
void dfs(int v, int par)
{
for(auto p : g[v])
{
if(p.fr == par) continue;
xr[p.fr] = xr[v] + 1;
pr[p.fr] = MP(v, p.sc);
dfs(p.fr, v);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n = N, m = U.size();
for (int i = 0; i < m; i++)
{
w.ad(0);
g[U[i]].ad(MP(V[i], i));
g[V[i]].ad(MP(U[i], i));
}
sum = ask(w);
dfs(0, 0);
for (int i = 1; i < n; i++)
{
fp.ad(MP(xr[i], pr[i].sc));
//cout << pr[i].sc << " ";
}
sort(fp.begin(), fp.end());
reverse(fp.begin(), fp.end());
int l = 0, r = m - 1, ans = 0;
while(l <= r)
{
int mid = (l + r) / 2;
for (int i = 0; i < m; i++) w[i] = 0;
for (int i = 0; i <= mid; i++) w[fp[i].sc] = 1;
if(ask(w) == sum) l = mid + 1;
else ans = mid, r = mid - 1;
}
if(xr[U[fp[ans].sc]] > xr[V[fp[ans].sc]]) ans = U[fp[ans].sc];
else ans = V[fp[ans].sc];
int S = ans;
//cout << S << endl;
for (int i = 0; i < m; i++) w[i] = 0;
int v = ans;
while(v)
{
w[pr[v].sc] = 1;
v = pr[v].fr;
}
lli sm = ask(w);
int s = (sm - sum) / (B - A);
v = ans;
for (int i = 0; i < s; i++)
{
col[pr[v].sc] = 1;
v=pr[v].fr;
}
l = 0, r = m - 1, ans = -1;
while(l <= r)
{
int mid = (l + r) / 2;
for (int i = 0; i < m; i++) w[i] = col[i];
for (int i = 0; i <= mid; i++) w[fp[i].sc] = 1;
if(ask(w) == sm) l = mid + 1;
else ans = mid, r = mid - 1;
}
if(ans == -1) ans = v;
else if(xr[U[fp[ans].sc]] > xr[V[fp[ans].sc]]) ans = U[fp[ans].sc];
else ans = V[fp[ans].sc];
int T = ans;
answer(S, T);
}
