#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 3e2;
vector<pair<int, int>> g[MAXN];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
for (int i = 0; i < M; i++){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
vector<int> w(M, 0);
ll onlyA = ask(w);
int ind = 0;
int l = 0, r = M - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 0);
for (int i = 0; i <= mid; i++) w[i] = 1;
ll res = ask(w);
if (res != onlyA){
ind = mid;
r = mid - 1;
} else l = mid + 1;
}
int u = U[ind], v = V[ind];
/*for (int i = 0; i < g[U[ind]].size(); i++){
if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
}
for (int i = 0; i < g[V[ind]].size(); i++){
if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
}*/
queue<int> q;
vector<bool> used(N, false);
vector<int> p(N, 0);
used[u] = true;
q.push(u);
vector<int> edges;
while (!q.empty()){
int x = q.front(); q.pop();
for (auto e : g[x]){
int y = e.first, i = e.second;
if (!used[y]){
used[y] = true;
q.push(y);
p[y] = i;
edges.push_back(i);
}
}
}
int S = -1, T = -1;
l = 0, r = edges.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 1);
for (int i = 0; i <= mid; i++) w[edges[i]] = 0;
ll res = ask(w);
if (res == onlyA){
int i = edges[mid];
if (p[U[i]] == i) S = U[i]; else
S = V[i];
r = mid - 1;
} else l = mid + 1;
}
fill(all(used), false);
fill(all(p), 0);
used[v] = true;
q.push(v);
edges.clear();
while (!q.empty()){
int x = q.front(); q.pop();
for (auto e : g[x]){
int y = e.first, i = e.second;
if (!used[y]){
used[y] = true;
q.push(y);
p[y] = i;
edges.push_back(i);
}
}
}
l = 0, r = edges.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 1);
for (int i = 0; i <= mid; i++) w[edges[i]] = 0;
ll res = ask(w);
if (res == onlyA){
int i = edges[mid];
if (p[U[i]] == i) T = U[i]; else
T = V[i];
r = mid - 1;
} else l = mid + 1;
}
cerr << S << ' ' << T << endl;
answer(S, T);
}
