#include "highway.h"
#include <bits/stdc++.h>
#define MAXN 90005
#define MAXM 130005
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int N, M, pathLength, S, T;
ll A, B;
vector < int > U, V, Q;
vector < pii > Graph[MAXN];
vector < pair < int, pii > > nodes;
bool bin ( int x )
{
fill ( Q.begin(), Q.begin() + x + 1, 1 );
fill ( Q.begin() + x + 1, Q.end(), 0 );
ll tmp = ask ( Q );
if ( tmp != A * pathLength )
return true;
return false;
}
bool bin2 ( int x )
{
fill ( Q.begin(), Q.end(), 1 );
for ( int i = x; i < nodes.size(); i++ )
Q[nodes[i].second.first] = 0;
ll tmp = ask ( Q );
return (tmp == B * pathLength);
}
void dfs ( int node, int parent = -1, int depth = 0 )
{
for ( auto i : Graph[node] )
if ( i.first != parent )
dfs ( i.first, node, depth + 1 ), nodes.push_back ( {depth, {i.second, i.first}} );
}
int solve ( int node )
{
sort ( nodes.begin(), nodes.end() );
int s = 0, e = nodes.size(), mid, val, ans;
while ( s <= e )
{
mid = (s + e) / 2;
val = bin2 ( mid );
if ( val )
ans = mid, e = mid - 1;
else
s = mid + 1;
}
if ( ans == 0 )
return node;
return nodes[ans - 1].second.second;
}
void find_pair ( int _N, vector<int> _U, vector<int> _V, int _A, int _B )
{
N = _N;
M = _U.size();
A = _A;
B = _B;
swap ( U, _U );
swap ( V, _V );
for ( int i = 0; i < M; i++ )
{
Graph[U[i]].push_back ( {V[i], i} );
Graph[V[i]].push_back ( {U[i], i} );
}
Q.resize ( M );
if ( M == N - 1 )
{
//Graph is a tree, 51 points
for ( auto &i : Q )
i = 0;
pathLength = ask ( Q ) / A;
int s = 0, e = M - 1, mid, val, edge;
while ( s <= e )
{
mid = (s + e) / 2;
val = bin ( mid );
if ( val )
edge = mid, e = mid - 1;
else
s = mid + 1;
}
nodes.clear();
dfs ( U[edge], V[edge] );
S = solve ( U[edge] );
nodes.clear();
dfs ( V[edge], U[edge] );
T = solve ( V[edge] );
answer ( S, T );
}
}
