#include "highway.h"
#include <bits/stdc++.h>
#include <vector>
#include <string.h>
#define pb push_back
#define MAXM 130100
#define MAXN 90100
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int toask[MAXM] , M , N , A , B , dpt2[MAXN] , dpt1[MAXN] , vis[MAXN];
int v1[MAXN] , v2[MAXN] , d1[MAXM] , d2[MAXM] , iss , dist;
vector<int> w,bad;
vector< int > adj[MAXN] , adj1[MAXN] , adj2[MAXN] , deg1[MAXN] , deg2[MAXN] , deg[MAXN];
queue <pii> q1 , q2;
ll assk;
int toggle(int c){
return (c==0)?1:0;
}
int bsearch(int arr[]){
//cout << "cool" << endl;
vector<int>u,val,ori,ori1;val.clear(); u.clear();
for(int i=0; i<M; i++){
val.pb(0);
if(arr[i] == 1) {u.pb(i);}
}
ll bfo = (iss==1) ? (ll)dist*B:assk;
int lo = 0 , hi = u.size()-1;
ori.resize(M,0);
ori1.resize(M,1);
while(lo < hi){
//cout << lo << " " << hi << endl;
int mid = (lo+hi)/2;
if(iss != 1) val= ori;
else val = ori1;
for(int i=lo; i<=mid; i++) val[u[i]] = toggle(val[u[i]]);
ll cur = ask(val);
if(cur == bfo) lo = mid + 1;
else hi = mid;
}
//cout << "wow " << lo << " " << u.size() << endl;
return u[lo];
}
void dfs(int cur , int pr){
//cout << cur << " " << "D" <<endl;
//system("PAUSE");
vis[cur] = 1;
for(int i=0; i<adj1[cur].size(); i++){
if(vis[adj1[cur][i]] == 0) {
w[deg1[cur][i]] = 1;
dfs(adj1[cur][i] , cur);
}
}
}
void bfs1(int cur , int d){
queue <pii> q; q.push({cur,0});
while(!q.empty()){
pii tp = q.front();q.pop();
int node = tp.first , dst = tp.second;
vis[node] = 1;
for(int i=0; i<adj1[node].size(); i++)
if(vis[adj1[node][i]] == 0){
q.push({adj1[node][i] , dst+1});
if(dst == d-1) toask[deg1[node][i]] = 1;
}
}
}
void bfs2(int cur , int d){
queue <pii> q; q.push({cur,0});
while(!q.empty()){
pii tp = q.front();q.pop();
int node = tp.first , dst = tp.second;
vis[node] = 1;
for(int i=0; i<adj2[node].size(); i++)
if(vis[adj2[node][i]] == 0){
q.push({adj2[node][i] , dst+1});
if(dst == d-1) toask[deg2[node][i]] = 1;
}
}
}
void find_pair(int n , vector<int> U , vector<int> V , int a , int b){
M = U.size();N = n;A = a;B=b;
for(int i=0; i<M; i++){
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
deg[U[i]].pb(i);
deg[V[i]].pb(i);
}
w.resize(M , 0);
assk = ask(w);
dist = (int)(assk/(ll)A);
//cout << assk << endl;
memset(toask , 0 ,sizeof toask);
for(int i=0; i<M; i++) toask[i] = 1;
int edg = bsearch(toask);
for(int i=0; i<M; i++) w[i] = 0;
q1.push({U[edg],0});q2.push({V[edg],0});
while(!q1.empty() || !q2.empty()){
//cout << q1.size() << " " << q2.size() << endl;
if(!q1.empty()){
pii t1 = q1.front();q1.pop();
int cur1 = t1.first;
v1[cur1] = 1;
d1[cur1] = t1.second;
//if(cur1 == 9396 || cur1 == 4410) cout << t1.second << " C" <<endl;
for(int i=0; i<adj[cur1].size(); i++){
if(v1[adj[cur1][i]] == 0) {
q1.push({adj[cur1][i],t1.second+1});
}
}
}
if(!q2.empty()){
pii t2 = q2.front();q2.pop();
int cur2 = t2.first;
//if(cur2 == 9396 || cur2 == 4410) cout << t2.second << " C" <<endl;
v2[cur2] = 1;
d2[cur2] = t2.second;
for(int i=0; i<adj[cur2].size(); i++){
if(v2[adj[cur2][i]] == 0) {
q2.push({adj[cur2][i],t2.second+1});
}
}
}
}
//cout << d1[4410] << " " << d1[9396] << endl;
//cout << d2[4410] << " " << d2[9396] << endl;
//cout << "cool2" << endl;
for(int i=0; i<M; i++){
//cout << i << " " << d1[U[i]] << " " << d1[V[i]] << " " << d2[U[i]] << " " << d2[V[i]] << endl;
if(d1[U[i]] < d2[U[i]] && d1[V[i]] < d2[V[i]]) {
//f(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "1 : " << i << endl;
adj1[U[i]].pb(V[i]);
adj1[V[i]].pb(U[i]);
deg1[U[i]].pb(i);
deg1[V[i]].pb(i);
}
else if(d1[U[i]] > d2[U[i]] && d1[V[i]] > d2[V[i]]) {
//if(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "2 : " << i << endl;
adj2[U[i]].pb(V[i]);
adj2[V[i]].pb(U[i]);
deg2[U[i]].pb(i);
deg2[V[i]].pb(i);
}
else{
if(i != edg)bad.push_back(i);
}
}
for(int i=0; i<N; i++)
for(int j=0; j<adj1[i].size(); j++) w[deg1[i][j]] = 1;
for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
ll assk1 = ask(w);
int patu = (int)(((ll)assk1-assk)/((ll)B-A));
int patv = dist - patu - 1;
//cout << assk1 << " " << assk << " " << edg << " " << U[edg] << " " << V[edg] << " " << dist << " " << patu << " " << patv << endl;
int edgu ,edgv , s , t;
if(patu != 0){
memset(toask , 0 ,sizeof toask);
//for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1;
memset(vis , 0 ,sizeof vis);
bfs1(U[edg] , patu);
iss = 1;
edgu = bsearch(toask);
if(d1[U[edgu]] > d1[V[edgu]]) s = U[edgu];
else s = V[edgu];
}
else s = U[edg];
if(patv != 0){
memset(toask , 0 , sizeof toask);
//for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1;
memset(vis , 0 ,sizeof vis);
bfs2(V[edg] , patv);
edgv = bsearch(toask);
if(d2[U[edgv]] > d2[V[edgv]]) t = U[edgv];
else t = V[edgv];
}
else t = V[edg];
//cout << s << " " << t << endl;
answer(s,t);
}
