#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,timer=0;
vector<vector<pair<int,int>>>g;
vector<int>es,en,tour;
void dfs(int a,int b)
{
es[a]=timer;timer++;
for(auto i:g[a])
{
if(i.first!=b)
{
tour.push_back(i.second);
dfs(i.first,a);
}
}
en[a]=timer-1;
}
bool check(int a,int b)
{
return es[a]<=es[b]&&en[b]<=en[a];
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B) {
n=N;
m=U.size();
g.resize(n);
es.resize(n);
en.resize(n);
for(int i=0;i<m;i++)
{
g[U[i]].push_back({V[i],i});
g[V[i]].push_back({U[i],i});
}
vector<int>v(m);
long long sum=ask(v);
dfs(0,0);
int l=0,r=m-1;
while(r>l)
{
int mid=(l+r+1)/2;
for(int i=mid;i<m;i++)v[tour[i]]=1;
long long temp=ask(v);
for(int i=mid;i<m;i++)v[tour[i]]=0;
if(temp!=sum)l=mid;
else r=mid-1;
}
int x,y;
if(check(U[tour[l]],V[tour[l]]))x=V[tour[l]];
else x=U[tour[l]];
while(!tour.empty())tour.pop_back();
timer=0;
dfs(x,x);
l=0;r=m-1;
while(r>l)
{
int mid=(l+r+1)/2;
for(int i=mid;i<m;i++)v[tour[i]]=1;
long long temp=ask(v);
for(int i=mid;i<m;i++)v[tour[i]]=0;
if(temp!=sum)l=mid;
else r=mid-1;
}
if(check(U[tour[l]],V[tour[l]]))y=V[tour[l]];
else y=U[tour[l]];
answer(x,y);
}
