#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int n = N, m = U.size();
vector <vector<ar<int,2>>> adj(n);
for ( int i = 0; i < m; i++ ){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
vector <int> w(m);
i64 C = ask(w);
bool isSplitted = false;
vector <int> blocked(m);
ar <int,2> ans = {-1, -1};
vector <int> s(n), f(n), cut(n);
auto dfs = [&](auto dfs, int u, int p) -> void{
s[u] = 1;
f[u] = cut[u];
for ( auto &[v, j]: adj[u] ){
if ( v != p && !blocked[j] ){
dfs(dfs, v, u);
f[u] += f[v];
s[u] += s[v];
}
}
};
auto get = [&](auto get, int u, int p, int des) -> int{
for ( auto &[v, j]: adj[u] ){
if ( v != p && !blocked[j] ){
if ( s[v] >= des ){
return get(get, v, u, des);
}
}
}
return u;
};
vector <int> tmp; // stores edges
auto trav = [&](auto trav, int u, int p) -> void{
for ( auto &[v, j]: adj[u] ){
if ( v != p && !blocked[j] ){
tmp.pb(j);
trav(trav, v, u);
}
}
};
auto dec = [&](auto dec, int rt) -> void{
dfs(dfs, rt, -1);
int u = get(get, rt, -1, s[rt] / 2); // centroid
dfs(dfs, u, -1);
if ( s[u] == 1 ){
swap(ans[0], ans[1]);
ans[0] = u;
return;
}
int nxt = -1, mx = -1, it = -1;
for ( auto &[v, j]: adj[u] ){
if ( blocked[j] ) continue;
if ( chmax(mx, s[v]) ){
nxt = v, it = j;
}
}
//~ cout << "Cur centroid : " << u << ln;
//~ cout << " cut -> " << nxt << ln;
assert(it != -1);
blocked[it] = true;
w[it] = 1;
i64 cur = ask(w);
w[it] = 0;
if ( isSplitted ){
if ( cur == C ){ // cost didn't change
if ( f[nxt] > 0 ){
dec(dec, nxt);
} else dec(dec, u);
} else{
if ( f[nxt] == 0 ){
cut[nxt] = 1;
dec(dec, nxt);
} else{
cut[u] = 1;
dec(dec, u);
}
}
} else{
if ( cur != C ){
isSplitted = true;
cut[u] = cut[nxt] = 1;
dec(dec, u), dec(dec, nxt);
} else{
trav(trav, nxt, u);
for ( auto &x: tmp ){
w[x] = 1;
}
i64 T = ask(w);
for ( auto &x: tmp ){
w[x] = 0;
} tmp.clear();
if ( T != C ){
dec(dec, nxt);
} else{
dec(dec, u);
}
}
}
};
dec(dec, 0);
//~ cout << "Answer : "; cout << ans[0] << " " << ans[1] << ln;
answer(ans[0], ans[1]);
}
