#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;
int toask[MAXM] , M , N , A , B , dpt[MAXN] , vis[MAXN];
vector<int> w;
vector< int > adj[MAXN] , deg[MAXN];
ll assk;
int toggle(int c){
return (c==0)?1:0;
}
int bsearch(int arr[]){
vector<int>u,val;val.clear(); u.clear();
for(int i=0; i<M; i++){
val.pb(0);
if(arr[i] == 1) {u.pb(i);}
}
ll bfo = assk;
int lo = 0 , hi = u.size()-1;
while(lo < hi){
//cout << lo << " " << hi << endl;
int mid = (lo+hi)/2;
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;
bfo = cur;
}
//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<adj[cur].size(); i++){
if(adj[cur][i] != pr && vis[adj[cur][i]] == 0) {
w[deg[cur][i]] = 1;
dfs(adj[cur][i] , cur);
}
}
}
void dfs1(int cur , int pr , int cnt , int d){
//cout << "dfs1 " << cur << " " << pr << " " << cnt << endl;
dpt[cur] = d;
for(int i=0; i<adj[cur].size(); i++)
if(adj[cur][i] != pr) {
if(cnt == 1) toask[deg[cur][i]] = 1;
dfs1(adj[cur][i] , cur , cnt-1 , d+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;
if(N == M) {answer(1,3);return;}
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);
int dist = (int)(assk/(ll)A);
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;
dfs(U[edg] , V[edg]);
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 = U[edg],edgv = V[edg] , s , t;
if(patu != 0){
memset(toask , 0 ,sizeof toask);
dfs1(U[edg] , V[edg] , patu , 0);
edgu = bsearch(toask);
if(dpt[U[edgu]] > dpt[V[edgu]]) s = U[edgu];
else s = V[edgu];
}
else s = U[edg];
if(patv != 0){
memset(toask , 0 , sizeof toask);
dfs1(V[edg] , U[edg] , patv , 0);
edgv = bsearch(toask);
if(dpt[U[edgv]] > dpt[V[edgv]]) t = U[edgv];
else t = V[edgv];
}
else t = V[edg];
//cout << edgu << " " << edgv << endl;
answer(s,t);
}
