#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MAXN = 90000;
int n, m, tIn[MAXN], timer;
vector<int> u, v, adj[MAXN];
void Dfs(int u, int p) {
tIn[u] = timer++;
for(int v : adj[u])
if (v != p)
Dfs(v, u);
}
long long MyAsk(int l, int r){
vector<int> w(m);
for(int i = 0; i < m; i++)
if ((l <= tIn[u[i]] && tIn[u[i]] <= r) || (l <= tIn[v[i]] && tIn[v[i]] <= r))
w[i] = 1;
else
w[i] = 0;
return ask(w);
}
int Find_city() {
assert(timer == n);
long long allA = MyAsk(-1, -1);
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (MyAsk(mid + 1, r) != allA)
l = mid + 1;
else
r = mid;
}
for(int i = 0; i < n; i++)
if (tIn[i] == l)
return i;
assert(0);
}
void find_pair(int _n, vector<int> _u, vector<int> _v, int a, int b) {
n = _n;
u = _u;
v = _v;
m = u.size();
assert(m == n - 1);
for(int i = 0; i < m; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
timer = 0;
Dfs(0, -1);
int s = Find_city();
timer = 0;
Dfs(s, -1);
int t = Find_city();
answer(s, t);
}
