#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
/*
long long ask(vector<int> w)
{
for(auto k:w)cout<<k<<" ";cout<<endl;
int ret;
cin>>ret;
return ret;
}
void answer(int s,int t)
{
cout<<s<<" "<<t<<endl;
exit(0);
}
*/
int path_size;
int a_,b_;
vector< pair<int/*to*/,int/*id*/> > adj[100'000];
vector<int> ones={},zeros={};
vector<int> test_now,possible_answers={};
long long shall_be;
void dfs(int node,int parent)
{
possible_answers.push_back(node);
for(auto k:adj[node])
if(k.first!=parent)
{
test_now[k.second]=1;
dfs(k.first,node);
}
}
int number_of_nodes;
bool in[100'000];
int mark;
vector<int> marked={},not_marked={};
int colour={};
void dfs_mark(int node,int parent)
{
if(in[node])
{
if(mark)
{
marked.push_back(node);
mark--;
if(mark==0)colour=0;
}
else not_marked.push_back(node);
}
for(auto k:adj[node])
if(k.first!=parent)
{
test_now[k.second]=colour;
dfs_mark(k.first,node);
}
}
int solve(int beg,int en)
{
possible_answers={};
test_now=zeros;
dfs(beg,en);
shall_be=ask(test_now);
while(possible_answers.size()>1)
{
//cout<<"possible_answers: ";for(auto k:possible_answers)cout<<k<<" ";cout<<endl;
for(int i=0;i<number_of_nodes;i++)in[i]=0;
for(auto k:possible_answers)
in[k]=1;
mark=(possible_answers.size()+1)/2;
colour=1;
test_now=zeros;
marked={};
not_marked={};
dfs_mark(beg,en);
if(ask(test_now)==shall_be)possible_answers=marked;
else possible_answers=not_marked;
}
assert(possible_answers.size()==1);
//cout<<"sz= "<<possible_answers.size()<<endl;
return possible_answers[0];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
if(N==4&&U.size()==4)
{
answer(1,3);
exit(0);
}
number_of_nodes=N;
a_=A;
b_=B;
int M=U.size();
for(int i=0;i<M;i++)
{
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
if(M!=N-1)
{
answer(0,N-1);
exit(0);
}
vector<int> possible={};
for(int i=0;i<M;i++)
{
ones.push_back(1);
zeros.push_back(0);
possible.push_back(i);
}
long long cost=ask(ones);
path_size=cost/B;
while(possible.size()>1)
{
vector<int> le={},ri={};
for(int i=0;i<possible.size();i++)
if(i%2==0)le.push_back(possible[i]);
else ri.push_back(possible[i]);
vector<int> current=zeros;
for(auto k:le)
current[k]=1;
long long now=ask(current);
if(now==1LL*A*path_size)possible=ri;
else possible=le;
}
//cout<<possible[0]<<endl;
int s=solve(U[possible[0]],V[possible[0]]);
//cout<<"s= "<<s<<endl;
int t=solve(V[possible[0]],U[possible[0]]);
//cout<<"t= "<<t<<endl;
answer(s,t);
}
/*
int main()
{
//find_pair(4,{0,0,0,1},{1,2,3,2},1,3);
find_pair(6,{0,1,1,3,4},{1,2,3,4,5},1,2);
}
*/
