#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
vector<pair<int,int>> adj[150000];
int ver[150000];
int are[150000];
int visitados[150000];
int contador;
void dfs(int s){
for(auto u: adj[s]){
if(visitados[u.f]==0){
visitados[u.f]++;
are[u.s]=contador;
ver[contador]=u.f;
contador++;
dfs(u.f);
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M=U.size();
if(M==N-1||1){
vector<int> w(M,0);
ll tamanho=ask(w);
for(int i=0; i<M; i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
int l=0, r=N-2, m;
while(l<r){
m=(l+r)/2;
for(int i=0; i<M; i++){
if(i<=m) w[i]=1;
else w[i]=0;
}
if(ask(w)!=tamanho){
r=m;
}else{
l=m+1;
}
}
//partimos o gráfico pela aresta l, logo os
//vertices das duas arvores que sobram serao
//os extremos da aresta l;
int a=U[l], b=V[l];
memset(visitados, 0, sizeof(visitados));
memset(ver,-1, sizeof(ver));
memset(are,-1,sizeof(are));
visitados[b]=visitados[a]=1;
contador=0;
dfs(a);
int ans1, ans2;
l=-1;
r=N-2;
while(l<r){
m=(l+r+1)/2;
for(int i=0; i<M; i++){
if(are[i]>=m) w[i]=1;
else w[i]=0;
//cout<<w[i]<<' ';
}
//cout<<'\n';
if(ask(w)!=tamanho){
l=m;
}else{
r=m-1;
}
}
ans1=l;
if(ans1==-1) ans1=a;
else ans1= ver[ans1];
memset(visitados, 0, sizeof(visitados));
memset(ver,-1, sizeof(ver));
memset(are,-1,sizeof(are));
visitados[b]=visitados[a]=1;
contador=0;
dfs(b);
l=-1;
r=N-2;
while(l<r){
m=(l+r+1)/2;
for(int i=0; i<M; i++){
if(are[i]>=m) w[i]=1;
else w[i]=0;
//cout<<w[i]<<' ';
}
//cout<<'\n';
if(ask(w)!=tamanho){
l=m;
}else{
r=m-1;
}
}
ans2=l;
if(ans2==-1) ans2=b;
else ans2= ver[ans2];
//for(int i=0; i<M; i++) cout<<are[i]<<' '; cout<<'\n';
//for(int i=0; i<M; i++) cout<<ver[i]<<' '; cout<<'\n';
//for(auto u: are) cout<<u<<' '; cout<<'\n';
answer(ans1, ans2);
//cout<<"->"<<ans1<<' '<<ans2<<'\n';
}else{
}
}
/*
5 4 16 20 1 4
0 1
1 2
2 3
3 4
****************
5 4 16 20 1 3
0 1
1 2
2 3
3 4
****************
5 4 16 20 0 2
0 1
1 2
2 3
3 4
****************
5 4 16 20 3 4
0 1
1 2
2 3
3 4
*/
/*
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M=U.size();
ll tamanho;
vector<int> w(M,0);
ll ultima=ask(w), atual;
tamanho=(ultima/A);
w[0]=1;
int l=0, r=N-2, m;
while(l<r){
m=(l+r)/2;
for(int i=0; i<M; i++){
if(i<=m){
w[i]=0;
}else{
w[i]=1;
}
//cout<<w[i]<<' ';
}
//cout<<"->"<<m<<'\n';
atual=ask(w);
if(atual==ultima){
r=m-1;
}else if(atual/B==ultima/A){
l=m+1;
}else{
r=m;
}
}
//cout<<l<<' '<<l+tamanho<<'\n';
answer(l, l+tamanho);
}
*/
