#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// ll ask(vector<int> w)
// void answer(int a, int b)
vector<vector<pair<int,int>>> adjlist; // node, ind
int n,a,b,m;
vector<int> parentedge;
vector<int> parentnode;
vector<int> preorder;
vector<bool> visited;
vector<bool> visitededge;
void dfs(int node, int par){
preorder.push_back(node);
visited[node]=true;
for (auto p : adjlist[node]){
int i = p.first;
int ni = p.second;
if (i==par||visited[i]){continue;}
parentnode[i]=node;
parentedge[i]=ni;
visitededge[ni]=true;
visited[i]=true;
dfs(i,node);
}
}
int findedgeind(int numedges, int initial){
int l = 0, r = numedges-1;
vector<int> ans;
while (l<=r){
int mid = (l+r)/2;
ans.assign(numedges,0);
for (int i = 0; i<=mid; i++){
ans[i]=1;
}
if (ask(ans)==initial){
l=mid+1;
} else {
r=mid-1;
}
}
return l;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;a=A;b=B;m=U.size();
adjlist.assign(n,vector<pair<int,int>>());
parentnode.resize(n,-1);
parentedge.resize(m,-1);
for (int i = 0; i<U.size(); i++){
adjlist[U[i]].push_back({V[i],i});
adjlist[V[i]].push_back({U[i],i});
//cout<<U[i]<<' '<<V[i]<<endl;
}
vector<int> query(m);
ll len = ask(query)/a;
int edgeind = findedgeind(m,len*a);
int root = U[edgeind];
visited.assign(n,false);
visitededge.assign(m,false);
query.assign(m,1);
parentnode[root]=-1;
parentedge[root]=-1;
dfs(root,-1);
// binary search until path is len*b
int l = 0, r = n-1;
query.assign(m,1);
while (l<=r){
int mid = (l+r)/2;
for (int i = 1; i<=mid; i++){
query[parentedge[preorder[i]]]=1;
}
for (int i = mid+1; i<n; i++){
query[parentedge[preorder[i]]]=0;
}
ll ans = ask(query);
if (ans<len*b){
l=mid+1;
} else {
r=mid-1;
}
}
root = preorder[l];
cout<<root<<endl;
// root at l, then search again
preorder.clear();
parentnode[root]=-1;
parentedge[root]=-1;
visited.assign(n,false);
visitededge.assign(m,false);
dfs(root,-1);
l = 0, r = n-1;
while (l<=r){
int mid = (l+r)/2;
for (int i = 1; i<=mid; i++){
query[parentedge[preorder[i]]]=1;
}
for (int i = mid+1; i<n; i++){
query[parentedge[preorder[i]]]=0;
}
ll ans = ask(query);
if (ans<len*b){
l=mid+1;
} else {
r=mid-1;
}
}
answer(root,preorder[l]);
}
