#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector < pair < int, int > > g[maxn];
int n, m;
ll a, b;
pair < int, int > ed[maxn];
vector < int > turn_active(vector < int > act)
{
vector < int > res(m, 1);
for (int v : act)
res[v] = 0;
return res;
}
vector < int > turn_inactive(vector < int > act)
{
vector < int > res(m, 0);
for (int v : act)
res[v] = 1;
return res;
}
int mark[maxn], from[maxn], dis[maxn];
int used[maxn], sp[maxn];
int sub_solve(int s, vector < int > st, ll sum, int idx)
{
for (int i = 0; i < m; i ++)
used[i] = 1e9, sp[i] = 0;
for (int v : st)
used[v] = -1;
used[s] = 0;
queue < int > q;
q.push(s);
from[s] = -1;
vector < int > d;
vector < int > base;
///exit(0);
while(!q.empty())
{
int v = q.front();
q.pop();
d.push_back(v);
for (pair < int, int > nb : g[v])
{
if (used[nb.first] == -1)
{
used[nb.first] = used[v] + 1;
from[nb.first] = nb.second;
sp[nb.second] = 1;
base.push_back(nb.second);
q.push(nb.first);
}
}
}
vector < int > forb;
for (int i = 0; i < m; i ++)
{
if (i == idx)
continue;
if (used[ed[i].first] != 1e9 && used[ed[i].second] != 1e9 && sp[i] == 0)
forb.push_back(i);
else
if (used[ed[i].first] == 1e9 && used[ed[i].second] != 1e9)
forb.push_back(i);
else
if (used[ed[i].first] != 1e9 && used[ed[i].second] == 1e9)
forb.push_back(i);
}
int lf = 1, rf = (int)(d.size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
vector < int > cur_set;
for (int i = max(1,mf); i < d.size(); i ++)
cur_set.push_back(from[d[i]]);
for (int v : forb)
cur_set.push_back(v);
if (ask(turn_inactive(cur_set)) != sum)
lf = mf + 1;
else
rf = mf - 1;
}
return d[rf];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
n = N;
m = U.size();
a = A;
b = B;
for (int i = 0; i < m; i ++)
{
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
ed[i] = {U[i], V[i]};
}
vector < int > act;
for (int i = 0; i < m; i ++)
act.push_back(i);
ll base_sum = ask(turn_active(act));
ll num_edges = base_sum / (ll)(A);
int lf = 0, rf = m - 1;
while(lf <= rf)
{
vector < int > cur;
int mf = (lf + rf) / 2;
for (int i = 0; i <= mf; i ++)
cur.push_back(i);
if (ask(turn_inactive(cur)) != num_edges * (ll)(A))
rf = mf - 1;
else
lf = mf + 1;
}
vector < int > ch;
ch.push_back(lf);
if (ask(turn_active(ch)) == num_edges * (ll)(B))
cout << "wtf" << endl;
int edge = lf;
///cout << "here " << edge << endl;
int v = V[edge], u = U[edge];
queue < int > q;
mark[v] = 1;
mark[u] = 2;
q.push(v);
q.push(u);
while(!q.empty())
{
int cur = q.front();
q.pop();
///cout << cur << " : " << mark[cur] << endl;
for (pair < int, int > nb : g[cur])
{
if (mark[nb.first] == 0)
{
mark[nb.first] = mark[cur];
q.push(nb.first);
}
}
}
vector < int > set_s, set_t;
for (int i = 0; i < n; i ++)
{
if (mark[i] == 1)
set_s.push_back(i);
else
set_t.push_back(i);
}
int S = sub_solve(v, set_s, base_sum, edge), T = sub_solve(u, set_t, base_sum, edge);
///cout << S << " " << T << " : " << v << " " << u << endl;
answer(S, T);
}
