#include "highway.h"
//#include "grader.cpp"
#include <set>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXLog = 18;
int n;
vector <int> graph[MAXN];
vector <pair <int, int>> edges;
bool inVector[MAXN];
long long askVector(vector <int> nodes)
{
for(int x: nodes) inVector[x] = true;
vector <int> v(edges.size());
for(int i = 0;i<edges.size();i++)
{
if(inVector[ edges[i].first ]==true && inVector[ edges[i].second ]==true) v[i] = 1;
else v[i] = 0;
}
//cout << " -> " << v.size() << '\n';
for(int x: nodes) inVector[x] = false;
return ask(v);
}
int parent[MAXN], depth[MAXN];
void DFSInit(int x, int last, int level)
{
parent[x] = last;
depth[x] = level;
for(int i = 0;i<graph[x].size();i++)
{
if(graph[x][i]==last)
{
graph[x].erase(graph[x].begin()+i);
break;
}
}
for(int y: graph[x])
{
DFSInit(y, x, level+1);
}
}
vector <int> bfsOrder;
void BFSInit(int x)
{
queue <int> q;
q.push(x);
while(q.empty()==false)
{
x = q.front();q.pop();
bfsOrder.push_back(x);
for(int y: graph[x])
{
q.push(y);
}
}
}
vector <int> getVector(vector <int> &v, int l, int r)
{
vector <int> out;
for(int i = l;i<=r;i++) out.push_back(v[i]);
return out;
}
pair <int, int> findLCA(long long A, long long B, long long pathLen)
{
int ind = 0;
for(int step = MAXLog;step>=0;step--)
{
if(ind+(1<<step)>=bfsOrder.size()) continue;
if(askVector(getVector(bfsOrder, 0, ind+(1<<step)))==pathLen*A) ind += (1<<step);
}
ind++;
return {bfsOrder[ind], parent[ bfsOrder[ind] ]};
}
void DFSMark(int x, int last, int excluded, vector <int> &v)
{
v.push_back(x);
for(int y: graph[x])
{
if(y==excluded) continue;
DFSMark(y, x, excluded, v);
}
}
int useTree(int root, int excluded, long long A, long long B, long long pathLen)
{
vector <int> v;
DFSMark(root,-1, excluded, v);
if(v.size()==1) return v[0];
//for(int x: v) cout << x << " ";
//cout << '\n';
long long base = askVector(v);
if(base==pathLen*A) return root;
int ind = 0;
for(int step = MAXLog;step>=0;step--)
{
if(ind+(1<<step)>=v.size()) continue;
if(askVector(getVector(v, 0, ind+(1<<step)))!=base) ind += (1<<step);
}
return v[ind+1];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
n = N;
for(int i = 0;i<U.size();i++)
{
graph[ U[i] ].push_back(V[i]);
graph[ V[i] ].push_back(U[i]);
edges.push_back({U[i], V[i]});
}
DFSInit(0, -1, 0);
BFSInit(0);
int pathLen = askVector({})/A;
pair <int, int> lcaPair = findLCA(A, B, pathLen);
int lca = lcaPair.second;
int rootS = lcaPair.first;
int S = useTree(rootS, -1, A, B, pathLen);
//cout << lca << " -- " << rootS << '\n';
//cout << S << '\n';
int T = -1;
if(depth[lca]-depth[S]==pathLen) T = lca;
else T = useTree(lca, rootS, A, B, pathLen);
//cout << T << '\n';
answer(S, T);
}
/*
6 5
1 2
1 5
0 1
0 2
1 3
1 4
2 5
*/
