#include <bits/stdc++.h>
#include "highway.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 9e4+5;
vector<ii> adj[maxn];
int ped[maxn];
int dep[maxn];
vector<int> buck[maxn];
int n, m;
void dfs(int u = 0, int p = -1, int d = 0)
{
dep[u] = d;
buck[d].pb(u);
for(auto kk : adj[u])
{
int v = kk.X, id = kk.Y;
if(v == p) continue;
ped[v] = id;
dfs(v, u, d+1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
n = N;
m = U.size();
for(int i = 0; i< m; i++)
{
adj[U[i]].pb(ii(V[i], i));
adj[V[i]].pb(ii(U[i], i));
}
ll base = ask(vector<int>(m, 0));
dfs();
int down = 0;
for(int i = 0; i< n; i++) down = max(down, dep[i]);
int lo = 0, hi = down;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
vector<int> send(m, 0);
for(int i = mid; i<= down; i++)
{
for(int u : buck[i])
{
send[ped[u]] = 1;
}
}
ll exp = ask(send);
// printf("try %d = %lld\n", mid, exp);
if(exp == base) hi = mid-1;
else lo = mid;
}
int reach = lo;
// printf("reach = %d\n", reach);
lo = 0, hi = ((int) buck[reach].size())-1;
while(lo< hi)
{
int mid = (lo+hi)/2;
vector<int> send(m, 0);
for(int i = 0; i<= mid; i++)
{
send[ped[buck[reach][i]]] = 1;
}
ll exp = ask(send);
if(exp == base) lo = mid+1;
else hi = mid;
}
int S = buck[reach][lo];
for(int i = 0; i<= down; i++) buck[i].clear();
ped[S] = -1;
dfs(S, -1, 0);
int reach2 = base/A;
lo = 0, hi = ((int) buck[reach2].size())-1;
// for(int i = 0; i< n; i++) printf("ped[%d] = %d\n", i, ped[i]);
while(lo< hi)
{
int mid = (lo+hi)/2;
vector<int> send(m, 0);
for(int i = 0; i<= mid; i++)
{
send[ped[buck[reach2][i]]] = 1;
}
ll exp = ask(send);
if(exp == base) lo = mid+1;
else hi = mid;
}
int T = buck[reach2][lo];
answer(S, T);
}
