#include "highway.h"
#include <iostream>
using namespace std;
long long int allc,ta[1300005],m,p[1300005],amoney,bmoney,t,cnt,n,tag[1300005],road[1300005],map[2600005][2],sumlength,length,point,startans=-1,endans=-1,tree[1300005],trueroad,start=-1,a[1000005],father[1000005][2];
unsigned long long int check()
{
vector<int> w(m);
for(int i=0;i<m;i++)
{
w[i]=p[i];
//if(allc==1)cout<<i<<" "<<w[i]<<" ";
}
long long int g=ask(w);
//cout<<g<<endl;
for(int i=0;i<m;i++)p[i]=0;
return g;
}
unsigned long long int find(int s,int e)
{
if(s==e)
{
start=s;
return 0;
}
int mid=(s+e)/2;
for(int i=s;i<=mid;i++)p[i]=1;
t=check();
if(t>cnt)find(s,mid);
else find(mid+1,e);
return 0;
}
unsigned long long int buildtree(int xx)
{
int pt=1,ppt=1;
ta[pt]=xx;
while(pt<=ppt)
{
int x=ta[pt];
int p=road[x];
int c=0;
while(p!=-1)
{
if(tag[map[p][0]]==0)
{
c=1;
ppt++;
tag[map[p][0]]=1;
father[map[p][0]][0]=x;
father[map[p][0]][1]=p/2;
//buildtree(map[p][0]);
ta[ppt]=map[p][0];
}
p=map[p][1];
}
if(c==0)
{
a[0]++;
a[a[0]]=x;
}
pt++;
}
return 0;
}
unsigned long long int findroad(int xx)
{
int tp=xx;
while(tp!=point && p[father[tp][1]]==0)
{
p[father[tp][1]]=1;
tp=father[tp][0];
}
return 0;
}
unsigned long long int findtwo(int s,int e)
{
//cout<<"二分"<<s<<" "<<e<<endl;
//for(int i=s;i<=e;i++)cout<<a[i]<<" ";
//cout<<endl;
if(s==e)
{
trueroad=a[s];
return 0;
}
for(int i=s;i<=(s+e)/2;i++)
{
findroad(a[i]);
}
long long int l=check();
l=(l-cnt)/(bmoney-amoney);
//if(l==cnt)findtwo((s+e)/2+1,e);
//for(int i=(s+e)/2+1;i<=e;i++)findroad(a[i]);
//int r=check();
if(l==length)findtwo(s,(s+e)/2);
else findtwo((s+e)/2+1,e);
return 0;
}
unsigned long long int findlength(int x)
{
int tp=x;
while(tp!=point)
{
sumlength++;
tp=father[tp][0];
}
return 0;
}
unsigned long long int findans(int x)
{
int tp=x;
while(length!=sumlength)
{
sumlength--;
tp=father[tp][0];
}
if(startans==-1)startans=tp;
else endans=tp;
return 0;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
amoney=A;
bmoney=B;
n=N;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
map[i*2][0]=V[i];
map[i*2][1]=road[U[i]];
road[U[i]]=i*2;
map[i*2+1][0]=U[i];
map[i*2+1][1]=road[V[i]];
road[V[i]]=i*2+1;
}
for(int i=0;i<m;i++)p[i]=0;
cnt=check();
find(0,m-1);
//cout<<V[start]<<" "<<U[start]<<endl;
tag[V[start]]=1;
tag[U[start]]=1;
point=U[start];
buildtree(point);
//cout<<endl;
//cout<<point<<endl;
for(int i=1;i<=a[0];i++)
{
//cout<<a[i]<<" ";
findroad(a[i]);
}
length=(check()-cnt)/(bmoney-amoney);
//cout<<endl;
findtwo(1,a[0]);
findlength(trueroad);
//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
findans(trueroad);
point=V[start];
a[0]=0;
tag[point]=1;
sumlength=0;
buildtree(point);
//cout<<endl;
//cout<<point<<endl;
//cout<<"第二個點"<<endl;
for(int i=1;i<=a[0];i++)
{
//cout<<a[i]<<" ";
findroad(a[i]);
}
//cout<<endl;
allc=1;
length=check();
length=(length-cnt)/(bmoney-amoney);
allc=0;
//cout<<length<<endl;
//cout<<endl;
findtwo(1,a[0]);
findlength(trueroad);
//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
findans(trueroad);
//cout<<startans<<" "<<endans<<endl;
answer(startans,endans);
}
