#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m;
ll dist,w1,w2,dist2;
vector <ii> adj[maxn];
ii e[maxn];
int d[maxn]; ii par[maxn];
int side[maxn], idx;
int dnc()
{
int l=0; int r=m-1;
while (l<r)
{
int mid=(l+r)/2;
vector <int> dau(m,0);
for (int i=0; i<=mid; i++) dau[i] = 1;
ll temp = ask(dau);
if (temp > dist) r = mid;
else l=mid+1;
}
return r;
}
int trace(int id1, int id2, vector <int> nodes, vector <int> nodes2)
{
int l=0; int r=nodes.size()-1;
while (l<r)
{
int mid = (l+r+1)/2;
vector <int> dau(m,1);
dau[idx] = 0;
for (int i=0; i<mid; i++) if (par[nodes[i]].ff!=-1) dau[par[nodes[i]].ss] = 0;
for (int i:nodes2) if (par[i].ff!=-1) dau[par[i].ss]=0;
if (ask(dau)>dist) l=mid;
else r=mid-1;
}
return nodes[l];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m=U.size(); n=N; w1=A; w2=B;
fill_n(side,n,0);
for (int i=0; i<n; i++) par[i]={-1,-1};
cerr<<":>"<<endl;
for (int i=0; i<n; i++) adj[i].clear();
for (int i=0; i<m; i++) e[i].ff=U[i], e[i].ss = V[i], adj[e[i].ff].push_back({e[i].ss,i}), adj[e[i].ss].push_back({e[i].ff,i});
vector <int32_t> dau(m,0);
dist=ask(dau);
cerr<<dist<<endl;
idx = dnc();
cerr<<idx<<endl;
fill_n(d,n,-1);
int u=e[idx].ff; int v=e[idx].ss;
d[u]=d[v]=0; par[u] = par[v] = {-1,-1};
dau[idx] = -1;
queue<int> q;
q.push(u); q.push(v);
side[u] = 1; side[v] = 2;
vector <int> nodes[3];
nodes[1].push_back(u);
nodes[2].push_back(v);
while (!q.empty())
{
int u=q.front(); q.pop();
for (ii i:adj[u])
{
int v=i.ff; int id = i.ss;
if (d[v]==-1)
{
par[v] = {u,id};
side[v] = side[u];
d[v] = d[u]+1;
// cerr<<u<<" - "<<v<<endl;
dau[id] = side[v];
nodes[side[v]].push_back(v);
q.push(v);
}
}
}
answer(trace(1,2,nodes[1],nodes[2]), trace(2,1,nodes[2],nodes[1]));
}
