#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 9e4 + 5;
int n, m, a, b;
vector<int>u, v, g[lim];
namespace sub1234{
void solve(){
vector<int>pie(n), h(n);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& i : g[s]){
if(i != pie[s]){
int d = u[i] ^ v[i] ^ s;
pie[d] = i;
h[d] = h[s] + 1;
dfs(d);
}
}
};
ll init = ask(vector<int>(m, 0));
auto work = [&] (int start){
fill(pie.begin(), pie.end(), -1);
h[start] = 0;
dfs(start);
vector<int>p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return h[i] > h[j];
});
int low = 0, high = n - 2, ans;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>w(m, 0);
for(int i = 0; i <= mid; i++){
w[pie[p[i]]] = 1;
}
if(ask(w) > init){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
return p[ans];
};
int s = work(0);
answer(s, work(s));
}
}
namespace sub56{
vector<int>tree[lim];
void solve(){
ll init = ask(vector<int>(m, 0));
int low = 0, high = n - 1, root;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>w(m, 0);
for(int i = 0; i <= mid; i++){
for(int& j : g[i]){
w[j] = 1;
}
}
if(ask(w) > init){
high = (root = mid) - 1;
}
else{
low = mid + 1;
}
}
vector<bool>vis(n, false);
queue<int>q;
q.push(root);
vis[root] = true;
while(!q.empty()){
int s = q.front();
q.pop();
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(!vis[d]){
tree[s].push_back(i);
tree[d].push_back(i);
vis[d] = true;
q.push(d);
}
}
}
vector<int>pie(n), h(n);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& i : tree[s]){
if(i != pie[s]){
int d = u[i] ^ v[i] ^ s;
pie[d] = i;
h[d] = h[s] + 1;
dfs(d);
}
}
};
int dst = init / a, s;
auto work = [&] (int start, bool first_start){
vector<int>pre_h;
if(!first_start){
pre_h = h;
}
fill(pie.begin(), pie.end(), -1);
h[start] = 0;
dfs(start);
vector<int>p;
for(int i = root; i < n; i++){
if(i == start){
continue;
}
if(first_start){
if(h[i] >= (dst >> 1)){
p.push_back(i);
}
}
else if(h[i] == dst && pre_h[i] == dst - pre_h[s]){
p.push_back(i);
}
}
sort(p.begin(), p.end(), [&] (int i, int j){
return h[i] > h[j];
});
int low = 0, high = int(p.size()) - 1, ans;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>w(m, 0);
for(int i = 0; i <= mid; i++){
for(int& j : g[p[i]]){
w[j] = 1;
}
}
if(ask(w) > init){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
return p[ans];
};
s = work(root, true);
answer(s, work(s, false));
}
}
void find_pair(int _n, vector<int>_u, vector<int>_v, int _a, int _b){
n = _n;
swap(u, _u);
swap(v, _v);
a = _a;
b = _b;
m = u.size();
for(int i = 0; i < m; i++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
if(m == n - 1){
sub1234::solve();
}
else{
sub56::solve();
}
}
