#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
using ll = long long;
struct edge_t{
int u, v;
};
const int N = 90'000 + 5, M = 130'000 + 5;
int n, m;
vector <edge_t> edge;
vector <int> adj[N];
vector <int> vquery;
namespace subtask12{
bool check(){
return m == n - 1;
}
int pv[N];
int pe[N];
int ctrtour, tour[N];
void dfs_tour(int u){
tour[ctrtour] = u;
ctrtour++;
for (auto i: adj[u]){
auto v = u ^ edge[i].u ^ edge[i].v;
if (v == pv[u]){
continue;
}
pv[v] = u;
pe[v] = i;
dfs_tour(v);
}
}
int solve_fixed(int s){
pv[s] = -1;
pe[s] = -1;
ctrtour = 0;
dfs_tour(s);
fill(vquery.begin(), vquery.end(), 1);
ll length_path = ask(vquery);
int lo = 1, hi = n - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int pos = 1; pos <= mid; pos++){
vquery[pe[tour[pos]]] = 1;
}
if (ask(vquery) == length_path){
hi = mid;
}
else{
lo = mid + 1;
}
}
return tour[lo];
}
void solve(){
int s = 0;
int t = solve_fixed(s);
answer(s, t);
}
}
void find_pair(int _n, vector <int> _u, vector <int> _v, int a, int b){
n = _n;
m = isz(_u);
edge.resize(m);
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
edge[i] = edge_t{u, v};
adj[u].emplace_back(i);
adj[v].emplace_back(i);
}
vquery.resize(m);
if (subtask12::check()){
subtask12::solve();
return;
}
}
