#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int,int>>> adj;
int m;
int n;
vector<int> _U, _V;
int cw = -1;
int len = -1;
vector<int> dists(int i) {
vector<int> dist(n, -1);
queue<int> q;
q.push(i);
dist[i] = 0;
while(!q.empty()) {
int v = q.front(); q.pop();
for(auto &e : adj[v]) {
int u = e.first;
if(dist[u] != -1) continue;
dist[u] = dist[v] + 1;
q.push(u);
}
}
return dist;
}
pair<int,int> fle(int start, int banned) {
vector<pair<int,int>> S;
queue<int> q;
vector<int> dist(n, -1);
q.push(start);
dist[start] = 0;
while(!q.empty()) {
int v = q.front(); q.pop();
int d = dist[v];
for(auto &e : adj[v]) {
int eid = e.second;
int u = e.first;
if(u == banned || dist[u] != -1) continue;
S.push_back({d+1, eid});
dist[u] = d + 1;
q.push(u);
}
}
sort(S.rbegin(), S.rend());
vector<int> asdf(m, 0);
int sz = S.size();
for(int i = 0; i < sz; i++) {
asdf[S[i].second] = 1;
}
if(ask(asdf) == cw) return {start,start};
int lo = 0;
int hi = sz-1;
while(hi - lo > 2) {
int p = (hi+lo)/2;
vector<int> Q(m,0);
for(int j = 0; j <= p; j++) {
Q[S[j].second] = 1;
}
if(ask(Q) == cw) {
lo = p+1;
} else {
hi = p;
}
}
int EDGE = -1;
for(int y = lo; y <= hi; y++) {
vector<int> Q(m,0);
for(int j = 0; j <= y; j++) {
Q[S[j].second] = 1;
}
if(ask(Q) > cw) {
EDGE = S[y].second;
break;
}
}
return {_U[EDGE], _V[EDGE]};
}
int eor() {
int lo = 0;
int hi = m-1;
while(hi - lo > 2) {
int p = (hi+lo)/2;
vector<int> Q(m, 0);
for(int j = 0; j <= p; j++) {
Q[j] = 1;
}
if(ask(Q) > cw) {
hi = p;
} else {
lo = p+1;
}
}
for(int y = lo; y <= hi; y++) {
vector<int> Q(m, 0);
for(int j = 0; j <= y; j++) Q[j] = 1;
if(ask(Q) > cw) return y;
}
}
ll simple() {
vector<int> Q(m, 0);
return ask(Q);
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b) {
n = N;
m = U.size();
_U = U;
_V = V;
adj.resize(N);
for(int i = 0; i < m; i++) {
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
cw = simple();
len = cw/(static_cast<ll>(a));
int seid = eor();
int u = U[seid];
int v = V[seid];
pair<int,int> ss = fle(u,v);
pair<int,int> tt = fle(v,u);
vector<int> s1d = dists(ss.first);
vector<int> s2d = dists(ss.second);
int s,t;
if(s1d[tt.first] == len) {
s = ss.first;
t = tt.first;
} else if(s1d[tt.second] == len) {
s = ss.first;
t = tt.second;
} else if(s2d[tt.first] == len) {
s = ss.second;
t = tt.first;
} else {
s = ss.second;
t = tt.second;
}
answer(s,t);
}
