#include<bits/stdc++.h>
#define MAXN 100007
#include "highway.h"
using namespace std;
int n,m,dep[MAXN],from,to,st,et,parent[MAXN];
bool ok;
vector< pair<int,int> > v[MAXN];
vector<int> euler,euler2;
vector<int> w;
void dfs(int x,int p){
dep[x]=dep[p]+1;
parent[x]=p;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
euler.push_back(v[x][i].second);
dfs(v[x][i].first,x);
}
}
void dfss(int x,int p){
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
euler2.push_back(v[x][i].second);
dfss(v[x][i].first,x);
}
}
int pref(int x){
for(int i=0;i<=x;i++)w[euler[i]]=1;
for(int i=x+1;i<m;i++)w[euler[i]]=0;
return ask(w);
}
int pref2(int x){
for(int i=0;i<=x;i++)w[euler2[i]]=1;
for(int i=x+1;i<m;i++)w[euler2[i]]=0;
return ask(w);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n=N; m=int(U.size());
for(int i=1;i<=m;i++){
v[U[i-1]+1].push_back({V[i-1]+1,i-1});
v[V[i-1]+1].push_back({U[i-1]+1,i-1});
}
dfs(1,0);
for(int i=1;i<=n;i++){
reverse(v[i].begin(),v[i].end());
}
dfss(1,0);
w.resize(m);
for(int i=0;i<m;i++)w[i]=1;
long long path=ask(w);
int l=-1,r=int(euler.size()),tt;
while(l+1<r){
tt=(l+r)/2;
if(pref(tt)==path){
r=tt;
}else{
l=tt;
}
}
to=r;
l=-1; r=int(euler2.size());
while(l+1<r){
tt=(l+r)/2;
if(pref2(tt)==path){
r=tt;
}else{
l=tt;
}
}
from=r;
st=euler2[from]; et=euler[to];
if(st==et){
if(dep[U[st]+1]>dep[V[st]+1])swap(U[st],V[st]);
U[st]++;
for(int i=0;i<path/B-1;i++)U[st]=parent[U[st]];
U[st]--;
answer(U[st],V[st]);
return;
}
if(dep[U[st]+1]>dep[V[st]+1])swap(U[st],V[st]);
if(dep[U[et]+1]>dep[V[et]+1])swap(U[et],V[et]);
answer(V[st],V[et]);
return;
}
