#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
vector<pii> G[N];
vector<int> H[N];
int E[N], dep[N], rem[N];
int T, fnt[N];
void DFS(int u, int p = -1, int d = 0){
dep[u] = d;
T ++;
for(auto adj : H[u])
if(adj != p)
DFS(adj, u, d + 1);
T ++;
fnt[u] = T;
}
void find_pair(int _n, vector<int> U, vector<int> V, int A, int B){
int n = _n;
int m = U.size();
//assert(m == n - 1);
for(int i = 0; i < m; i++){
G[U[i]].pb({V[i], i});
G[V[i]].pb({U[i], i});
}
vector<int> W(m, 0);
ll dis = ask(W);
int src = -1;
cerr << "*&^%$ " << dis << '\n';
vector<int> I2(n, 0);
iota(all(I2), 0);
{
int L = 0, R = n;
while(L + 1 < R){
int mid = (L + R) >> 1;
for(int i = 0; i < mid; i++) rem[I2[i]] = 1;
for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
//cerr << "^ " << mid << ' ';
//for(auto x : W) cerr << x;
//cerr << '\n';
if(ask(W) > dis) R = mid;
else L = mid;
for(int i = 0; i < mid; i++) rem[I2[i]] = 0;
}
src = I2[L];
}
//src = 0;
cerr << "@ " << src << '\n';
for(int i = 0; i < src; i++) rem[i] = true;
queue<int> Q;
vector<int> D(n, n);
D[src] = 0; Q.push(src);
int fr;
while(!Q.empty()){
fr = Q.front(); Q.pop();
for(auto ed : G[fr]){
int adj = ed.F;
if(rem[adj]) continue;
if(D[adj] > D[fr] + 1){
D[adj] = D[fr] + 1;
H[fr].pb(adj);
H[adj].pb(fr);
//cerr << "E : " << fr << ' ' << adj << '\n';
Q.push(adj);
}
}
}
DFS(src);
vector<int> I;
for(int i = 0; i < n; i++) if(D[i] == n) rem[i] = 1;
for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);
sort(all(I), [&](int i, int j){
return dep[i] > dep[j];
});
//cerr << "() " ;
//for(auto x : I) cerr << x << ' ';
//cerr << '\n';
int st = -1, fn = -1;
int L = 0, R = I.size();
while(L + 1 < R){
int mid = (L + R) >> 1;
//for(int i = 0; i < m; i++) W[i] = 0;
for(int i = 0; i < mid; i++) rem[I[i]] = 1;
for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
if(ask(W) > dis) R = mid;
else L = mid;
for(int i = 0; i < mid; i++) rem[I[i]] = 0;
}
st = I[L];
for(int i = 0; i < L; i++) rem[I[i]] = 1;
//cerr << "!! " << st << '\n';
if(1ll * A * D[st] == dis){
answer(src, st);
return ;
}
I.clear();
for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);
DFS(st);
sort(all(I), [&](int i, int j){
return dep[i] > dep[j];
});
//cerr << "! " << st << ' ' << L << '\n';
//cerr << "&&& ";
//for(auto x : I) cerr << x;
//cerr << '\n';
assert(I.size() >= 2);
//reverse(I.begin(), I.end() - 1);
L = 0, R = I.size();
while(L + 1 < R){
int mid = (L + R) >> 1;
//for(int i = 0; i < m; i++) W[i] = 0;
for(int i = 0; i < mid; i++) rem[I[i]] = 1;
for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
//cerr << "^ " << mid << ' ';
//for(auto x : W) cerr << x;
//cerr << '\n';
if(ask(W) > dis) R = mid;
else L = mid;
for(int i = 0; i < mid; i++) rem[I[i]] = 0;
//for(int i = 0; i < n; i++) cerr << rem[i];
//cerr << '\n';
}
fn = I[L];
cerr << "!! " << fn << '\n';
assert(1ll * A * (D[fn] + D[st]) == dis);
answer(st, fn);
}
