#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 90000 + 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];
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
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);
memset(h, -1, sizeof h);
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;
par[u] = v;
}
}
for (int i = 0; i < n; i++)
p[i] = i;
sort(p, p+n, [](int A, int B){
return h[A] > h[B];
});
int S = -1, T = -1;
for (int _ = 0; _ < 2; _++){
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];
if (mark[v])
continue;
for (auto [u,idx] : g[v])
Q[idx] |= 1;
}
ll nowCost = ask(Q);
for (int i = 0; i <= mid; i++){
int v = p[i];
if (mark[v])
continue;
for (auto [u,idx] : g[v])
Q[idx] &= 0;
}
if (nowCost == Cost)
L = mid;
else
R = mid;
}
if (_ == 0){
S = p[R];
int x = S;
while (h[x] > 0){
mark[x] = 1;
x = par[x];
}
}
else
T = p[R];
}
answer(S,T);
}
