#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e5+5;
long long normal;
vector<int>adj[mxN];
vector<int>x,y;
void answer(int s, int t);
long long ask(const std::vector<int> &w);
void color(int u, int c, int e = -1) {
if(c) x.push_back(u);
else y.push_back(u);
for(auto z : adj[u]) if(z != e) {
color(z, 1-c, u);
}
}
int mxDist;
vector<int>p[mxN];
vector<int>re(mxN);
map<pair<int,int>,int>id;
void dfs(int node, int dist, int e = -1) {
mxDist = max(mxDist, dist);
if(e > -1) p[dist].push_back(id[{node, e}]);
re[node] = dist;
for(auto z : adj[node]) if(z != e) dfs(z, dist+1, node);
}
int M_;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int search_point(vector<int>points) {
int n = (int)points.size();
int ans = -1;
int l = 0, r = n-1;
while(l <= r) {
int mid = (l+r)/2;
vector<int>Ask(M_, 0);
for(int i = l ; i <= mid ; i++)
Ask[points[i]] = 1;
long long R = ask(Ask);
if(R != normal) {
r = mid-1;
ans = mid;
} else l = mid+1;
}
return (ans == -1 ? ans : points[ans]);
}
void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
const int m = (int)u.size();
M_ = m;
vector<int>dummy(m, 0);
normal = ask(dummy);
for(int i = 0 ; i < n-1 ; i++)
id[{u[i], v[i]}] = id[{v[i], u[i]}] = i, adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
color(0, 0);
int len = normal / a;
vector<int>w = x;
while((int)w.size() > 1) {
//shuffle(w.begin(), w.end(), rng);
if(w.size() == 2) {
vector<int>Ask(m, 0);
for(auto z : adj[w[0]])
Ask[id[{w[0], z}]] = 1;
if(((ask(Ask) - normal) / (b - a)) & 1)
break;
swap(w[0], w[1]);
vector<int>Ask2(m, 0);
for(auto z : adj[w[0]])
Ask2[id[{w[0], z}]] = 1;
if(((ask(Ask2) - normal) / (b - a)) & 1)
break;
w = y;
continue;
}
int mid = (int)w.size()/2;
vector<int>Ask(m, 0);
for(int i = 0 ; i < mid ; i++) {
for(auto z : adj[w[i]])
Ask[id[{w[i], z}]] = 1;
}
if(((ask(Ask) - normal) / (b - a)) & 1) {
while(w.size() > mid)
w.pop_back();
}
}
int node = w[0];
dfs(node, 0);
int R = search_point(p[len]);
int P = (re[u[R]] > re[v[R]] ? u[R] : v[R]);
answer(node, P);
}
