#include "highway.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 6e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const int INF = 2e9;
const int MOD = 1e9+87;
const int MOD2 = 1e9+7;
const int LOG = 30;
int n, a, b, m, x, y, val[MAXN];
vector<pii> adj[MAXN];
vector<int> vec; // urutan
void dfs2(int nw, int pa){
if(nw != 1) vec.pb(nw);
for(int i=adj[nw].size()-1; i>=0; i--){
auto [nx, wei] = adj[nw][i];
if(nx==pa) continue;
val[nx] = wei;
dfs2(nx, nw);
}
}
void dfs(int nw, int pa){
if(nw != 1) vec.pb(nw);
for(auto [nx, wei] : adj[nw]){
if(nx==pa) continue;
val[nx] = wei;
dfs(nx, nw);
}
}
ll DIS, MX;
ll ceksuff(int mid){
vector<int> w(m, 0);
for(int i=0; i<=mid; i++){
int idx = vec[i];
w[val[idx]] = 1;
}
return ask(w);
}
ll cek(int mid){
vector<int> w(m, 0);
for(int i=0; i<=mid; i++){
int idx = vec[i];
w[val[idx]] = 1;
}
return ask(w);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N; a = A; b = B; m = U.size();
for(int i=0; i<m; i++){
adj[U[i]+1].pb({V[i]+1, i});
adj[V[i]+1].pb({U[i]+1, i});
}
dfs(1,0);
vector<int> w(m, 0);
DIS = ask(w) / a;
MX = cek(vec.size()-1); // kalo semua jadi b
{
// cout << mx << " mx\n";
int l=0, r=vec.size()-1, mid=0, cnt=-1;
while(l<=r){
mid = md;
if(cek(mid) == MX) cnt = mid, r = mid-1;
else l = mid+1;
}
if(cnt == -1) assert(false);
// cout << cnt << ' '<< vec[cnt] << ' '<< cek(4)<<' '<<MX << " cnt\n";
y = vec[cnt];
// cout << y <<" y\n";
}
vec.clear();
dfs2(1,0);
// for(auto in : vec) cout << in << " in\n";
{
int l=0, r=vec.size()-1, mid=0, cnt=-1;
while(l<=r){
mid = md;
if(ceksuff(mid) == MX) cnt = mid, r = mid-1;
else l = mid+1;
}
if(cnt == -1) assert(false);
// cout << cnt << ' '<< vec[cnt] << ' '<< ceksuff(4) << " cnt\n";
x = vec[cnt];
// cout << x <<" x\n";
}
int lca = 1;
if(x==y) x = lca;
// cout << x << ' '<< y << "Xy\n";
answer(x-1, y-1);
}
