#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
struct node
{
vector<pair<int, int>> edges; // to number;
bool been = false;
int depth;
};
vector<node> g;
std::vector<int> w;
long long lastanswer = 0;
/*
vector<int> maketree(int root, vector<int> U, vector<int> V) //returns translation layer
{
for (int i = 0; i < g.size(); i++)
g[i].been = false;
vector<int> trans;
queue<pair<int, int>> q; // node depth;
q.push({root, 0});
g[root].been = true;
while (!q.empty())
{
auto p = q.front();
q.pop();
g[p.first].depth = p.second;
for (auto i : g[p.first].edges)
{
if (g[i.first].been)
continue;
g[i.first].been = true;
trans.push_back(i.second);
q.push({i.first, p.second + 1});
}
}
return trans;
}
*/
pair<vector<int>, vector<int>> maketwotrees(int rootU, int rootV, int edgeon)
{
for (int i = 0; i < g.size(); i++)
g[i].been = false;
vector<int> rootedinU;
vector<int> rootedinV;
rootedinV.push_back(edgeon);
rootedinU.push_back(edgeon);
queue<tuple<int, int, bool>> q; // node depth;
q.push({rootU, 0, false});
q.push({rootV, 0, true});
g[rootU].been = true;
g[rootV].been = true;
while (!q.empty())
{
auto [to, depth, from] = q.front();
q.pop();
g[to].depth = depth;
for (auto i : g[to].edges)
{
if (g[i.first].been)
continue;
g[i.first].been = true;
(from ? rootedinV : rootedinU).push_back(i.second);
q.push({i.first, depth + 1, from});
}
}
return {rootedinU, rootedinV};
}
int binarysearnew(vector<int> translation, vector<int> inactive)
{
// trans translation
int b = 0;
int e = translation.size();
while (b + 1 != e)
{
fill(w.begin(), w.end(), 1);
for (int x : inactive)
w[x] = 0;
for (int x : translation)
w[x] = 0;
for (int i = (b + e) / 2; i < e; i++)
w[translation[i]] = 1;
long long tmp = ask(w);
if (tmp != lastanswer)
b = (b + e) / 2;
else
e = (b + e) / 2;
}
return translation[b];
}
/*
int binarysear(vector<int> translation)
{
// trans translation
int b = 0;
int e = translation.size();
while (b + 1 != e)
{
fill(w.begin(), w.end(), 1);
for (int x : translation)
w[x] = 0;
for (int i = (b + e) / 2; i < e; i++)
w[translation[i]] = 1;
long long tmp = ask(w);
if (tmp != lastanswer)
b = (b + e) / 2;
else
e = (b + e) / 2;
}
return translation[b];
}
*/
int binarysearPoints()
{
int b = 0;
int e = w.size();
fill(w.begin(), w.end(), 0);
while (b + 1 != e)
{
for (int i = (b + e) / 2; i < e; i++)
w[i] = 1;
long long tmp = ask(w);
if (tmp != lastanswer)
{
for (int i = (b + e) / 2; i < e; i++)
w[i] = 0;
b = (b + e) / 2;
}
else
e = (b + e) / 2;
}
return b;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
int M = U.size();
vector<int> inorderbfs(M);
g.resize(N);
w.resize(M);
for (int i = 0; i < U.size(); i++) // rebuild graph
{
g[U[i]].edges.push_back({V[i], i});
g[V[i]].edges.push_back({U[i], i});
}
fill(w.begin(), w.end(), 0);
lastanswer = ask(w);
//Punkt auf Pfad
int edgeonpath = binarysearPoints();
auto [Utranslation, Vtranslation] = maketwotrees(U[edgeonpath], V[edgeonpath],edgeonpath); // rooted in
// 1.Endpunkt
//inorderbfs = maketree(edgeinpath, U, V);
int endpointa, endpointb;
if (!Utranslation.empty())
{
int tmp = binarysearnew(Utranslation, Vtranslation);
endpointa = V[tmp];
if (g[U[tmp]].depth >= g[V[tmp]].depth)
endpointa = U[tmp];
assert(endpointa != -1);
}
else
endpointa = V[edgeonpath];
//2. Endpunkt
//inorderbfs = maketree(endpointa, U, V);
if (!Vtranslation.empty())
{
int tmp = binarysearnew(Vtranslation, Utranslation);
//tmp = binarysear(inorderbfs);
endpointb = U[tmp];
if (g[V[tmp]].depth >= g[U[tmp]].depth)
endpointb = V[tmp];
}
else
endpointa = U[edgeonpath];
answer(endpointa, endpointb);
}
