#include "highway.h"
#include <queue>
#include <stdint.h>
#include <cstdio>
#include <algorithm>
static const int INF=1e9+7;
static void dfs(int node,int parent,const std::vector<int>& elist,const std::vector<std::vector<int> >& adj,
std::vector<int>& post){
for(int e:adj[node]){
int child=elist[e^1];
if(child==parent) continue;
dfs(child,node,elist,adj,post);
post.push_back(e^1);
}
}
static int find_first_vertex(const std::vector<int>& elist,const std::vector<std::vector<int> >& adj,int64_t base,const std::vector<int>& mask,int root){
std::vector<int> post;
dfs(root,root,elist,adj,post);
/*
printf("postorder:\n");
for(int i=0;i<post.size();i++){
printf(" %d=>%d\n",elist[post[i]],elist[post[i]^1]);
}
*/
int low=0,high=post.size();
while(high-low>1){
int mid=(low+high)/2;
std::vector<int> ws(mask);
for(int i=0;i<mid;i++){
ws[post[i]>>1]=1;
}
if(ask(ws)>base){
high=mid;
}else{
low=mid;
}
}
//printf("critical tree edge: %d=>%d\n",elist[post[low]],elist[post[low]^1]);
return elist[post[low]];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
int64_t base=ask(std::vector<int>(M));
//printf("BASE=%ld\n",base);
std::vector<int> elist;
std::vector<std::vector<int> > adj(N);
for(int i=0;i<M;i++){
elist.push_back(U[i]);
elist.push_back(V[i]);
adj[U[i]].push_back(i*2);
adj[V[i]].push_back(i*2+1);
}
int low=0,high=M;
while(high-low>1){
int mid=(low+high)/2;
std::vector<int> ws(M);
for(int i=0;i<mid;i++){
ws[i]=1;
}
if(ask(ws)>base){
high=mid;
}else{
low=mid;
}
}
//printf("critical: %d<=>%d\n",U[low],V[low]);
std::vector<int> from(N);
std::queue<int> frontier;
std::vector<int> dist(N,INF);
dist[U[low]]=0;
frontier.push(U[low]);
dist[V[low]]=0;
frontier.push(V[low]);
while(!frontier.empty()){
int node=frontier.front();
frontier.pop();
for(int e:adj[node]){
if((e>>1)<low) continue;
int child=elist[e^1];
if(dist[child]==INF){
dist[child]=dist[node]+1;
from[child]=e;
frontier.push(child);
}
}
}
std::vector<int> ws(M,1);
adj.clear();
adj.resize(N);
for(int i=0;i<N;i++){
if(dist[i]!=0&&dist[i]!=INF){
int e=from[i];
int U=elist[e];
int V=elist[e^1];
adj[U].push_back(e);
adj[V].push_back(e^1);
ws[e>>1]=0;
}
}
adj[U[low]].push_back(low*2);
adj[V[low]].push_back(low*2+1);
ws[low]=0;
int S=find_first_vertex(elist,adj,base,ws,U[low]);
int T=find_first_vertex(elist,adj,base,ws,S);
//printf("S=%d, T=%d\n",S,T);
answer(S,T);
}
