#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[90002];
vector<int> w;
int now, M;
int bfsorder[90002];
bool visited[90002];
int dist[90002];
int K = -1, S = -1, T = -1;
int cnt = 0;
ll D;
void bfs(int x, int N, int p)
{
for(int i=0;i<N;i++) visited[i] = false;
for(int i=0;i<N;i++) dist[i] = 0;
visited[x] = true;
queue<int> q;
q.push(x);
while(!q.empty())
{
int curr = q.front();
q.pop();
if(!p) bfsorder[--now] = curr;
else if(dist[curr] = D) bfsorder[cnt++] = curr;
for(auto u : adj[curr])
{
int i = u.first, j = u.second;
if(!visited[i])
{
visited[i] = true;
dist[i] = dist[curr] + 1;
q.push(i);
}
}
}
}
void makezero()
{
for(int i=0;i<M;i++) w[i] = 0;
}
void binarysearch(int l, int r, ll zerotoll, int k)
{
if(l == r)
{
if(k == 0) K = bfsorder[l];
if(k == 1) S = bfsorder[l];
if(k == 2) T = bfsorder[l];
return;
}
int mid = (l + r)/2;
makezero();
for(int i=0;i<=mid;i++)
{
for(auto u : adj[bfsorder[i]])
{
w[u.second] = 1;
}
}
ll toll = ask(w);
if(toll > zerotoll) binarysearch(l, mid, zerotoll, k);
else binarysearch(mid+1, r, zerotoll, k);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
M = U.size();
for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); }
w.resize(M);
makezero();
ll zerotoll = ask(w);
D = zerotoll / A;
/*
now = N; bfs(0, N);
binarysearch(0, N-1, zerotoll, 0);
*/
now = N; bfs(0, N, 0);
binarysearch(0, N-1, zerotoll, 0);
now = N; bfs(K, N, 0);
binarysearch(0, N-1, zerotoll, 1);
now = N; bfs(S, N, 1);
binarysearch(0, cnt-1, zerotoll, 2);
answer(S, T);
}
