#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define rsort(a) {sort(all(a));reverse(all(a));}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
ll M=U.size();
vvp g(N);
rep(i,M){
g[U[i]].pb(V[i],i);
g[V[i]].pb(U[i],i);
}
vector<int> tmp(M);
ll dis=ask(tmp)/A;
vb dead(N,false);
ll rt=0;
vi sub(N),dep(N),par(N);
while(true){
vi al;
auto dfs=[&](auto && self,ll i,ll p,ll d) -> void {
al.pb(i);
sub[i]=1;dep[i]=d;
for(auto x:g[i])if(x.fi!=p&&!dead[x.fi]){
par[x.fi]=x.se;
self(self,x.fi,i,d+1);
sub[i]+=sub[x.fi];
}
};dfs(dfs,rt,-1,0);
if(al.size()==2){
answer(al[0],al[1]);
return;
}
ll sz=sub[rt];
auto find_cen=[&](auto && self,ll i,ll p) -> ll {
for(auto x:g[i])if(x.fi!=p&&!dead[x.fi]&&sub[x.fi]*2>sz)return self(self,x.fi,i);
return i;
};
rt=find_cen(find_cen,rt,-1);
dfs(dfs,rt,-1,0);
vp srt;
for(auto x:g[rt])if(!dead[x.fi])srt.pb(sub[x.fi],x.fi);
rsort(srt);
vi a,b;
ll cnta=0,cntb=0;
for(auto x:srt){
if(cnta<cntb){
swap(cnta,cntb);swap(a,b);
}
cntb+=x.fi;
b.pb(x.se);
}
vi color(N,-1);
auto dfs2=[&](auto && self,ll i,ll p,ll c) -> void {
color[i]=c;
for(auto x:g[i])if(x.fi!=p&&!dead[x.fi])self(self,x.fi,i,c);
};
for(ll x:a)dfs2(dfs2,x,rt,0);
for(ll x:b)dfs2(dfs2,x,rt,1);
rep(i,M)tmp[i]=0;
rep(i,M)if((color[U[i]]==0||color[V[i]]==0)&&!dead[U[i]]&&!dead[V[i]])tmp[i]=1;
ll res=ask(tmp);
if(res==dis*A){
for(auto x:a)dead[x]=true;
}
else if(res==dis*B){
for(auto x:b)dead[x]=true;
}
else{
ll lena=(res-dis*A)/(B-A),lenb=dis-lena;
vi a,b;
rep(i,N)if(dep[i]==lena&&color[i]==0)a.pb(i);
rep(i,N)if(dep[i]==lenb&&color[i]==1)b.pb(i);
while(a.size()>1){
vi l,r;
rep(i,a.size()/2)l.pb(a[i]);
REP(i,a.size()/2,a.size())r.pb(a[i]);
rep(i,M)tmp[i]=0;
for(ll x:l)tmp[par[x]]=1;
if(ask(tmp)==dis*A)a=r;
else a=l;
}
while(b.size()>1){
vi l,r;
rep(i,b.size()/2)l.pb(b[i]);
REP(i,b.size()/2,b.size())r.pb(b[i]);
rep(i,M)tmp[i]=0;
for(ll x:l)tmp[par[x]]=1;
if(ask(tmp)==dis*A)b=r;
else b=l;
}
answer(a[0],b[0]);return;
}
}
}
long long ask(const std::vector<int> &w);
void answer(int s, int t);
