#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, int parent, vector< int > &index, vector< vector< pair<int,int> > > &Graph, int &curr, int lastEdge, vector< int > &EdgeToNode){
for(auto a: Graph[node]){
if(a.first == parent) continue;
dfs(a.first, node, index, Graph, curr, a.second, EdgeToNode);
}
index[curr++] = lastEdge;
if(lastEdge != -1) EdgeToNode[lastEdge] = node;
}
void search(int left, int right, int M, vector< int > &ans, vector< int > &EdgeToNode, vector< int > &index, int mark, int leftToFind){
if(left == right){
ans.push_back(EdgeToNode[index[left]]);
//cout << "FOUND " << EdgeToNode[index[left]] << endl;
return;
}
//cout << left << ' ' << right << endl;
vector< int > toAsk(M);
int mid = (left+right)/2;
//cout << "HERE " << endl;
for(int i = left; i<= mid; i++){
//cout << index[i] << ' ';
//cout << EdgeToNode[index[i]] << ' ';
toAsk[index[i]] = 1;
}
//cout << endl;
//cout << endl;
int rep = ask(toAsk);
//cout << "REP " << rep << endl;
if(rep > mark){
//cout << "YEP " << endl;
if(leftToFind == 1){
search(left, mid, M, ans,EdgeToNode,index, mark,leftToFind);
return;
}
for(int i = left; i<= mid; i++){
toAsk[index[i]] = 0;
}
for(int i = mid+1; i <= right; i++){
toAsk[index[i]] = 1;
}
rep = ask(toAsk);
if(rep > mark){
search(left, mid, M, ans,EdgeToNode,index, mark,1);
search(mid+1, right, M, ans,EdgeToNode,index, mark,1);
}else{
search(left, mid, M, ans,EdgeToNode,index, mark,1);
}
}else{
for(int i = left; i<= mid; i++){
toAsk[index[i]] = 0;
}
for(int i = mid+1; i <= right; i++){
toAsk[index[i]] = 1;
}
rep = ask(toAsk);
if(rep > mark) search(mid+1, right, M, ans,EdgeToNode,index, mark,leftToFind);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
vector< vector< pair<int, int> > > Graph(N);
for(int i = 0; i < M; i++){
Graph[U[i]].push_back({V[i],i});
Graph[V[i]].push_back({U[i],i});
}
int curr = 0;
vector< int > index(N);
vector< int > EdgeToNode(M);
dfs(0, -1, index, Graph, curr,-1, EdgeToNode);
vector< int > ans;
vector< int > toAsk(M);
int mark = ask(toAsk);
//cout << "OK" << endl;
search(0,M-1, M,ans,EdgeToNode,index, mark,2);
//cout << "OK" << endl;
if(ans.size() == 1){
ans.push_back(0);
}
//cout << ans[0] << ' ' << ans[1] << endl;
answer(ans[0], ans[1]);
}
