#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MAXN = 90010;
int n, m;
int A, B;
int depth[MAXN];
int ancEdge[MAXN];
lli dist;
vector<int> adj[MAXN];
vector<int> level[MAXN];
vector<int> indEdge[MAXN];
void DFSInit(int cur, int p, int d)
{
depth[cur] = d;
level[d].push_back( cur );
for(int i = 0 ; i < (int)adj[cur].size() ; i++)
{
int viz = adj[cur][i];
int ind = indEdge[cur][i];
if( viz == p ) continue;
ancEdge[viz] = ind;
DFSInit( viz , cur , d + 1 );
}
}
vector<int> activeNodes(int L, int R)
{
vector<int> c( m , 0 );
for(int p = L ; p <= R ; p++)
{
for(int i = 0 ; i < (int)level[p].size() ; i++)
{
int cur = level[p][i];
c[ ancEdge[cur] ] = 1;
}
}
return c;
}
vector<int> activeNodes(int L, int R, int d)
{
vector<int> c( m , 0 );
for(int i = L ; i <= R ; i++)
{
int cur = level[d][i];
c[ ancEdge[cur] ] = 1;
}
return c;
}
int findMaxDepth()
{
int l = 0;
int r = n - 1;
while( l < r )
{
int m = ( l + r )/2;
if( ask( activeNodes( 1 , m ) ) == dist*B ) r = m;
else l = m + 1;
}
return r;
}
int findNode(int depth)
{
int l = 0;
int r = (int)level[depth].size() - 1;
while( l < r )
{
int m = ( l + r )/2;
if( ask( activeNodes( 0 , m , depth ) ) != dist*A ) r = m;
else l = m + 1;
}
return level[depth][r];
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b)
{
A = a; B = b;
n = N; m = (int)U.size();
dist = ask( vector<int>( m , 0 ) )/A;
for(int i = 0 ; i < m ; i++)
{
adj[ U[i] ].push_back( V[i] );
adj[ V[i] ].push_back( U[i] );
indEdge[ U[i] ].push_back( i );
indEdge[ V[i] ].push_back( i );
}
DFSInit( 0 , 0 , 0 );
int maxDepth = findMaxDepth();
int S = findNode( maxDepth );
for(int i = 0 ; i < n ; i++)
level[i].clear();
DFSInit( S , S , 0 );
int T = findNode( dist );
answer( S , T );
}
