#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define ll int
typedef vector <ll> vi;
typedef pair <ll,ll > ii;
typedef vector <ii> vii;
#define sz(x) (ll)x.size()
#define pb push_back
#define F first
#define S second
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void tabb(ll n){
for (ll i= 0; i<n; i++) cout<<"\t";
}
void printVct(vi &v){
for (ll i=0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
void printVctPair(vii &v){
for (ll i=0; i<sz(v); i++){
cout<<"("<<v[i].F<<","<<v[i].S<<") ";
}
cout<<endl;
}
void printVct2D(vector<vi> &adj){
for (ll i=0; i<sz(adj); i++){
cout<<i<<": ";
for (ll j =0; j<sz(adj[i]); j++){
cout<<"("<<adj[i][j]<<"),";
}
cout<<endl;
}
cout<<endl;
}
void printVctPair2D(vector<vii> &adj){
for (ll i=0; i<sz(adj); i++){
for (ll j =0; j<sz(adj[i]); j++){
cout<<"("<<adj[i][j].F<<","<<adj[i][j].S<<"),";
}
cout<<endl;
}
cout<<endl;
}
vector <vii> adj;
ll n,m;
long long b; //all light case value
ll calls= 1;
void find_pair(int N, vi V, vi U, int A,int B) {
n = N; m = sz(U);
adj.assign(n, vii());
for (ll i=0; i<m ;i++){
adj[U[i]].pb(ii(V[i], i));
adj[V[i]].pb(ii(U[i], i));
}
vi v(m, 0);
b = ask(v);
ll l, r, mid;
//STEP 1 - Find node on path from S to T
l = 0, r = m-1;
while (l < r){
mid = MID;
v.assign(m, 0);
for (ll i = 0; i<=mid; i++)
v[i] = 1;
if (calls == 60){
cout<<"hello";
return;
}
calls++;
long long c = ask(v);
if (c > b) r = mid;
else l = mid+1;
}
ll p = U[l];
//STEP 2 - Find distance from S
vi disNode(n);
vector <vi> dis(n, vi());
ll h = 0;
queue <ii> q;
vi vis(n, 0);
q.push(ii(p,0));
while (!q.empty()){
ii f = q.front();
q.pop();
ll u = f.F;
ll level = f.S;
h = max(level, h);
disNode[u] = level;
vis[u] = 1;
for (ll i= 0; i<sz(adj[u]); i++){
if (!vis[adj[u][i].F]){
q.push(ii(adj[u][i].F,level+1));
dis[level+1].pb(adj[u][i].S);
}
}
}
//printVct2D(dis);
l = 1, r = h;
ll maxDis = 0;
while (l <= r){
mid = MID;
v.assign(m,0);
for (ll i =0; i<sz(dis[mid]); i++)
v[dis[mid][i]] =1;
if (calls == 60){
cout<<"hello";
return;
}
calls++;
long long c = ask(v);
if (c > b){
l = mid + 1;
maxDis = mid;
}
else{
r = mid - 1;
}
}
//STEP 3 - Find S
l = 0, r = sz(dis[maxDis]) -1;
while (l < r){
mid = MID;
v.assign(m, 0);
for (ll i=0; i<=mid; i++)
v[dis[maxDis][i]] = 1;
if (calls == 60){
cout<<"hello";
return;
}
calls++;
long long c = ask(v);
if (c > b) r = mid;
else l = mid + 1;
}
ll e2 = dis[maxDis][l],s;
if (disNode[U[e2]] > disNode[V[e2]]) s = U[e2];
else s = V[e2];
//STEP 4 - Find T
vi canditates;
ll st = b / A;
q.push(ii(s, 0));
vis.assign(n ,0);
while (!q.empty()){
ii f = q.front();
q.pop();
ll u = f.F;
ll level = f.S;
vis[u] =1 ;
disNode[u] = level;
for(ll i =0; i<sz(adj[u]); i++){
if (!vis[adj[u][i].F]){
q.push(ii(adj[u][i].F, level +1));
if (level + 1 == st){
canditates.pb(adj[u][i].S);
}
}
}
}
//printVct(canditates);
l = 0, r = sz(canditates)-1;
while (l < r){
mid = MID;
v.assign(m , 0);
for (ll i = 0; i<= mid; i++)
v[canditates[i]] = 1;
if (calls == 60){
cout<<"hello";
return;
}
calls++;
long long c = ask(v);
if (c > b) r = mid;
else l = mid+1;
}
ll e3 = canditates[l],t;
if (disNode[U[e3]] > disNode[V[e3]]) t = U[e3];
else t = V[e3];
//dbg2(e3, t);
//dbg2(s, t);
answer(s, t);
}
/*
14 13 2 5 3 10
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13
*/
