#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int dist_a[sz+5],dist_b[sz+5];
int FIND(vector<int>w,vector<int>candidates,int root,int edge){
memset(visited,0,sizeof(visited));
for(int x : candidates) visited[x] = 1;
w=vector<int>(w.size(),1);
visited[root] = 0;
queue<int>q; q.push(root);
vector<pi>v; v.emplace_back(pi(root,edge));
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(visited[nxt]){
visited[nxt] = 0;
v.emplace_back(pi(nxt,id));
q.push(nxt);
}
}
}
reverse(v.begin(),v.end());
for(pi p : v) w[p.second]=0;
ll d = ask(w);
int l = 0,r = v.size()-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[v[i].second] = 1;
if(ask(w) > d) r = M-1;
else l = M+1;
for(int i=0; i<=M; i++) w[v[i].second] = 0;
}
return v[l].first;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
for(int i=0; i<n; i++){
tree[i].clear();
visited[i] = 0;
dist_a[i] = dist_b[i] = 1e9;
}
int m = U.size();
for(int i=0; i<U.size(); i++){
int a = U[i],b = V[i];
tree[a].emplace_back(pi(b,i));
tree[b].emplace_back(pi(a,i));
}
vector<int>w(m,0);
ll d = ask(w);
int l = 0,r = m-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[i] = 1;
if(ask(w) > d) r = M-1;
else l = M+1;
for(int i=0; i<=M; i++) w[i] = 0;
}
int e = l;
int a = U[e],b = V[e];
dist_a[a] = 0;
queue<int>q; q.push(a);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_a[nxt] > dist_a[cur] + 1){
dist_a[nxt] = dist_a[cur] + 1;
q.push(nxt);
}
}
}
dist_b[b] = 0;
q.push(b);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_b[nxt] > dist_b[cur] + 1){
dist_b[nxt] = dist_b[cur] + 1;
q.push(nxt);
}
}
}
vector<int>c1,c2;
for(int i=0; i<n; i++){
if(dist_a[i] < dist_b[i]) c1.emplace_back(i);
if(dist_a[i] > dist_b[i]) c2.emplace_back(i);
}
answer(FIND(w,c1,a,e),FIND(w,c2,b,e));
}
