#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<ll,ll>
typedef long long ll;
const int _N = 90005;
vector<int> edges[_N];
vector<pii> edge[_N];
vector<pii> EDGES;
int n, m, a, b;
ll dist;
pii num(ll x){
ll dif = x-dist;
//~ cout << dif << '\n';
assert(dif%(b-a)==0);
return {dist - dif/(b-a),dif/(b-a)};
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n = N;
m = U.size();
a=A,b=B;
for(int i=0;i<m;i++){
edges[U[i]].pb(V[i]);
edges[V[i]].pb(U[i]);
edge[U[i]].pb({V[i],i});
edge[V[i]].pb({U[i],i});
EDGES.pb({U[i],V[i]});
}
vector<int> toask(m,0);
ll TMP = ask(toask);
dist = TMP;
int l=0,r=m-1;
while(l < r){
int mid = (l+r)>>1;
for(int i=0;i<=mid;i++)toask[i] = 1;
for(int i=mid+1;i<m;i++)toask[i] = 0;
auto [x, y] = num(ask(toask));
if(y == 0)l = mid+1;
else r = mid;
}
int root = EDGES[l].first;
vector<int> should_be_B;
vector<int> prohibited(m,0);
{
queue<pii> q;
vector<int> Dist(n,2e9);Dist[root] = 0;
q.push({root,root});
while(!q.empty()){
auto [u, p] = q.front();q.pop();
for(auto [to, ind] : edge[u]){
if(to == p)continue;
if(Dist[to] <= Dist[u]+1){
should_be_B.pb(ind);
prohibited[ind] = 1;
}else if(Dist[to] == 2e9){
Dist[to] = Dist[u] + 1;
q.push({to, u});
}
}
}
}
//~ cout << EDGES[l].first << ';' << EDGES[l].second << '\n';
//~ cout << l << '-' << r << '\n';
queue<int> q;
vector<bool> used(n,0);
q.push(root);used[root] = true;
vector<int> v;
vector<pii> vse;
while(!q.empty()){
int u = q.front();q.pop();
for(auto [to, ind] : edge[u]){
if(used[to] || prohibited[ind])continue;
used[to] = true;
vse.pb({u, to});
v.pb(ind);
q.push(to);
}
}
l=0,r=v.size()-1;
while(l < r){
int mid = (l+r)>>1;
for(int i=0;i<=mid;i++)toask[v[i]] = 0;
for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
for(auto x : should_be_B)toask[x] = 1;
auto [x, y] = num(ask(toask));
if(y != 0)l = mid+1;
else r = mid;
}
//~ cout << l << '-' << r << '\n';
//~ cout << EDGES[v[l]].first << ' ' << EDGES[v[l]].second << '\n';
//~ for(auto [x, y] : vse){
//~ cout << x << ';' << y << '\n';
//~ }
prohibited.assign(m,0);
should_be_B.clear();
int s = vse[l].second;
root = s;
{
queue<pii> q;
vector<int> Dist(n,2e9);Dist[root] = 0;
q.push({root,root});
while(!q.empty()){
auto [u, p] = q.front();q.pop();
for(auto [to, ind] : edge[u]){
if(to == p)continue;
if(Dist[to] <= Dist[u]+1){
should_be_B.pb(ind);
prohibited[ind] = 1;
}else if(Dist[to] == 2e9){
Dist[to] = Dist[u] + 1;
q.push({to, u});
}
}
}
}
vse.clear();
used.assign(n,0);
q.push(root);used[root] = true;
v.clear();
while(!q.empty()){
int u = q.front();q.pop();
for(auto [to, ind] : edge[u]){
if(used[to])continue;
used[to] = true;
vse.pb({u, to});
v.pb(ind);
q.push(to);
}
}
l=0,r=v.size()-1;
while(l < r){
int mid = (l+r)>>1;
for(int i=0;i<=mid;i++)toask[v[i]] = 0;
for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
for(auto x : should_be_B)toask[x] = 1;
auto [x, y] = num(ask(toask));
if(y != 0)l = mid+1;
else r = mid;
}
int t = vse[l].second;
//~ cout << s << ' ' << t << '\n';
answer(s,t);
return;
}
/*
7 6
1 2
3 4
0 2
0 3
3 4
2 6
2 5
2 1
5 4
1 2
4 2
0 1
0 2
0 3
0 4
3 2
100000 1000000000
0 1
1 2
1 0
*/
