// ~ Be Name Khoda ~ //
#include "highway.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
vector <int> tok, adj[maxn5], v, u, ver[2], ed[2], jda[maxn5];
ll len, h[maxn5];
int m, q[maxn5], par[maxn5], kh[maxn5], gooded;
int kparid[maxn5], parid[maxn5], kpar[maxn5];
ll pas[2][maxn5];
bool mark[maxn5], good[maxn5];
void bfs(int rt){
par[rt] = -1;
memset(h, -1, sizeof h);
int l = 0, r = 1;
q[0] = rt;
h[rt] = 0;
while(l < r){
int a = q[l++];
for(auto id : adj[a]){
int b = u[id] == a ? v[id] : u[id];
if(h[b] != -1)
continue;
//cout << "here " << a << ' ' << b << ' ' << id << endl;
q[r++] = b;
par[b] = a;
h[b] = h[a] + 1;
parid[b] = id;
}
}
}
void dfs(int v, int ty){
mark[v] = true;
//cout << v << ' ' << par[v] << endl;
for(auto id : jda[v]){
int u = (::u[id]) == v ? (::v[id]) : (::u[id]);
if(mark[u])
continue;
//cout << "in " << v << ' ' << u << ' ' << ty << endl;
dfs(u, ty);
ver[ty].pb(u);
ed[ty].pb(id);
}
}
ll get(int id, int ty){
if(pas[ty][id] == -1){
fill(all(tok), 1);
tok[gooded] = false;
for(auto u : ed[ty ^ 1])
tok[u] = false;
for(int i = id + 1; i < int(ed[ty].size()); i++)
tok[ed[ty][i]] = false;
pas[ty][id] = ask(tok);
}
return pas[ty][id];
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
memset(pas, -1, sizeof pas);
u = U;
v = V;
m = u.size();
for(int i = 0; i < m; i++){
adj[u[i]].pb(i);
adj[v[i]].pb(i);
}
int lo = -1, hi = m;
tok.resize(m);
fill(all(tok), 0);
len = ask(tok) / a;
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
fill(all(tok), 0);
fill(tok.begin(), tok.begin() + mid + 1, 1);
ll cost = ask(tok);
if(cost == len * a)
lo = mid;
else
hi = mid;
}
gooded = hi;
//cout << "ok " << hi << ' ' << u[hi] << ' ' << v[hi] << endl;
bfs(u[hi]);
for(int i = 0; i < n; i++){
kh[i] = h[i];
kpar[i] = par[i];
kparid[i] = parid[i];
}
bfs(v[hi]);
for(int i = 0; i < n; i++){
//cout << i << ' ' << kh[i] << ' ' << h[i] << ' ' << par[i] << ' ' << kpar[i] << endl;
if(h[i] < kh[i] && par[i] != -1)
jda[par[i]].pb(parid[i]);
if(h[i] > kh[i] && kpar[i] != -1){
//cout << "Pushing " << i << ' ' << kpar[i] << endl;
jda[kpar[i]].pb(kparid[i]);
}
}
int rt[2] = {u[hi], v[hi]};
memset(mark, false, sizeof mark);
//cout << rt[0] << ' ' << rt[1] << endl;
dfs(rt[0], 0);
dfs(rt[1], 1);
/*
for(int i = 0; i < n - 1; i++)
//cout << ed[i] << ' ' << ver[i] << endl;
//*/
////cout << "its " << hi << endl;
lo = -1; hi = ed[0].size();
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(get(mid, 0) == len * a)
lo = mid;
else
hi = mid;
}
int s = (hi == int(ed[0].size()) ? rt[0] : ver[0][hi]);
//cout << lo << ' ' << hi << ' ' << ed[0].size() << ' ' << s << endl;
lo = -1; hi = ed[1].size();
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(get(mid, 1) == len * a)
lo = mid;
else
hi = mid;
}
int t = (hi == int(ed[1].size()) ? rt[1] : ver[1][hi]);
//cout << t << ' ' << lo << ' ' << hi << ' ' << ed[1].size() << endl;
answer(s, t);
}
