#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector<int> Q;
ll Cost = 0;
int p[maxn], par[maxn];
vector<pair<int,int>> g[maxn];
bool mark[maxn];
int get(int L, int R){
if (L+1 == R)
return L;
int mid = (L + R) >> 1;
for (int v = L; v < mid; v++)
for (auto [u,idx] : g[v])
Q[idx] |= 1;
ll nowCost = ask(Q);
for (int v = L; v < mid; v++)
for (auto [u,idx] : g[v])
Q[idx] &= 0;
if (nowCost != Cost)
return get(L,mid);
else
return get(mid,R);
}
int Que[maxn], head = 0, tail = 0, h[maxn];
int n;
int Get(int v){
memset(h, -1, sizeof h);
tail = head = 0;
h[v] = 0, Que[head++] = v;
while (tail < head){
int v = Que[tail++];
for (auto [u,idx] : g[v])
if (h[u] == -1)
h[u] = h[v]+1, Que[head++] = u;
}
for (int i = 0; i < n; i++)
p[i] = i;
sort(p, p+n, [](int A, int B){
return h[A] > h[B];
});
int L = -1, R = n-1;
while (R-L > 1){
int mid = (L+R) >> 1;
for (int i = 0; i <= mid; i++){
int v = p[i];
for (auto [u,idx] : g[v])
Q[idx] |= 1;
}
ll nowCost = ask(Q);
for (int i = 0; i <= mid; i++){
int v = p[i];
for (auto [u,idx] : g[v])
Q[idx] &= 0;
}
if (nowCost == Cost)
L = mid;
else
R = mid;
}
return p[R];
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
::n = n;
int m = U.size();
Q.resize(m);
for (int i = 0; i < m; i++){
Q[i] = 0;
g[V[i]].push_back({U[i],i});
g[U[i]].push_back({V[i],i});
}
Cost = ask(Q);
int v = get(0, n);
int S = Get(v);
int T = Get(S);
answer(S,T);
}
