#include "highway.h"
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
const int maxN = 90'000;
const int light = 0;
const int heavy = 1;
const int INF = 1e9;
int N;
vector<int> U;
vector<int> V;
long long A;
long long B;
int M;
int getV(int u, int e)
{
return U[e] + V[e] - u;
}
vector<int> edge[maxN];
int middleEdge;
long long DA;
int X, Y;
const int Xtree = 0;
const int Ytree = 1;
const int notree = -1;
const int noedge = -1;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
N = n;
U = u;
V = v;
A = a;
B = b;
M = U.size();
for(int j = 0; j < M; j++)
{
edge[ U[j] ].push_back(j);
edge[ V[j] ].push_back(j);
}
DA = ask(vector<int>(M, light));
int lo = 0;
int hi = M-1;
while(lo != hi)
{
int mid = (lo+hi)/2;
vector<int> w(M);
for(int j = 0; j < M; j++)
{
if(j <= mid)
w[j] = heavy;
else
w[j] = light;
}
if(ask(w) > DA) hi = mid;
else lo = mid+1;
}
int middleEdge = lo;
cerr << middleEdge << '\n';
X = U[middleEdge]; //0
Y = V[middleEdge]; //1
vector<int> dist(N, INF);
vector<int> tree(N, notree);
vector<int> parentEdge(N, noedge);
dist[X] = 0;
tree[X] = Xtree;
parentEdge[X] = noedge;
dist[Y] = 0;
tree[Y] = Ytree;
parentEdge[Y] = noedge;
queue<int> tbv;
tbv.push(X);
tbv.push(Y);
vector<int> treelist[2];
while(!tbv.empty())
{
int P = tbv.front();
treelist[tree[P]].push_back(P);
tbv.pop();
for(int e: edge[P])
{
int Q = getV(P, e);
if(dist[P] + 1 >= dist[Q]) continue;
dist[Q] = dist[P] + 1;
tree[Q] = tree[P];
parentEdge[Q] = e;
tbv.push(Q);
}
}
// for(int i = 0; i < N; i++) cerr << dist[i] << ' ' << tree[i] << ' ' << parentEdge[i] << '\n';
vector<int> ans;
for(int Z = 0; Z < 2; Z++)
{
lo = 0;
hi = int(treelist[Z].size()) - 1;
// cerr << "Z = " << Z << '\n';
// if(Z == 1)
// for(int t: treelist[Z]) cerr << t << ' ';
// cerr << '\n';
// cerr << lo << ' ' << hi << '\n';
while(lo != hi)
{
int mid = (lo+hi)/2;
vector<int> w(M, heavy);
w[middleEdge] = light;
for(int i = 0; i < N; i++)
if(parentEdge[i] != noedge)
w[parentEdge[i]] = light;
// cerr << "mid = " << mid << '\n';
// for(int i = 0; i <= mid; i++)
// {
// if(parentEdge[ treelist[Z][i] ] != noedge)
// w[ parentEdge[ treelist[Z][i] ] ] = light;
// }
for(int i = mid+1; i <= hi; i++)
{
if(parentEdge[ treelist[Z][i] ] != noedge)
w[ parentEdge[ treelist[Z][i] ] ] = heavy;
}
// cerr << "query = ";
// for(int h: w) cerr << h << ' ';
// cerr << '\n';
if(ask(w) > DA)
lo = mid+1;
else
hi = mid;
// cerr << lo << ' ' << hi << '\n';
}
ans.push_back(treelist[Z][lo]);
}
answer(ans[0], ans[1]);
}
