#include "highway.h"
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
int M, N;
ll Ask(vector<int>Q) {
vector<int>W(M);
for (int i : Q) W[i] = 1;
ll res = ask(W);
for (int i : W) cerr << i << " ";
cerr << ": W " << res << endl;;
return res;
}
ll Ask(vector<int>Q, vector<int>P) {
for (int i : P) Q.emplace_back(i);
return Ask(Q);
}
const int MAXN = 1e5;
vector<int> order, was, d, U, V;
vector<pair<int,int>>g[MAXN];
void bfs(int root) {
d.assign(N, -1);
queue<int>q;
q.push(root);
d[root] = 0;
while (q.size()) {
int v = q.front(); q.pop();
for (auto [to, id] : g[v]) if (d[to] == -1) {
d[to] = d[v] + 1;
q.push(to);
if (U[id] != v) swap(U[id], V[id]);
was[id] = 1;
order.emplace_back(id);
}
}
}
int solve(int root) {
was.assign(M, 0);
assert((int)was.size() == M);
order.clear();
bfs(root);
vector<int>nu;
for (int i = 0 ; i < M ; ++ i) {
if (!was[i]) nu.emplace_back(i);
}
ll emp = Ask(nu);
assert((int)order.size() == N-1);
for (int i : order) cerr << i << " ";
cerr << ": order\n";
for (int i : nu) cerr << i << " ";
cerr << ": nu\n";
int l = 0, r = N - 2;
while (l < r) {
int m = (l + r + 1) / 2;
vector<int>cur;
for (int i = m ; i < N-1 ; ++ i) cur.emplace_back(order[i]);
if (Ask(cur, nu) != emp) {
l = m;
} else {
r = m - 1;
}
}
l = order[l];
int S = d[U[l]] > d[V[l]] ? U[l] : V[l];
return S;
}
void find_pair(int N_, vector<int> U_, vector<int> V_, int A, int B) {
M = U_.size();
N = N_;
U = U_;
V = V_;
cerr << N << " " << M << " " << A << " " << B << " given\n";
for (int i = 0 ; i < M ; ++ i) {
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
int S = solve(0);
int T = solve(S);
cerr << S << " " << T << " mine\n";
answer(S, T);
}
