// solution with 3.465 log N queries
#include "thief.h"
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int t, id;
};
vector<vector<int> > grouping(int m, const vector<vector<int> >& pack) {
int s = 0, p = -1;
for (int i = 0; i < int(pack.size()); i++) {
s += pack[i].size();
if (s * 2 >= m) {
p = i;
break;
}
}
vector<vector<int> > res(3);
for (int i = 0; i < int(pack.size()); i++) {
int z = (i < p ? 0 : i > p ? 2 : 1);
res[z].insert(res[z].end(), pack[i].begin(), pack[i].end());
}
sort(res.begin(), res.end(), [&](const vector<int>& v1, const vector<int>& v2) {
return v1.size() > v2.size();
});
double x = double(res[0].size()) / m;
if ((1 - x) * (1 - x) * (1 - x) - x * x < 0) {
// x > 0.43016...
res[1].insert(res[1].end(), res[2].begin(), res[2].end());
res.pop_back();
}
return res;
}
vector<vector<int> > make_sequence_tree(int N, int M, const vector<int>& U, const vector<int>& V) {
// step #1. make spanning tree
vector<vector<pair<int, int> > > G(N);
for (int i = 0; i < M; i++) {
G[U[i]].push_back({V[i], i});
G[V[i]].push_back({U[i], i});
}
vector<int> basev;
vector<bool> vis(N, false);
auto build_tree = [&](auto& self, int x) -> void {
vis[x] = true;
for (auto [y, id] : G[x]) {
if (!vis[y]) {
basev.push_back(id);
self(self, y);
}
}
};
build_tree(build_tree, 0);
// step #2. recursive building
vector<int> layer(M);
vector<vector<int> > f;
auto push = [&](int e, int subf) -> void {
if (layer[e] == f.size()) {
f.push_back(vector<int>(M, -1));
}
f[layer[e]++][e] = subf;
};
auto recur = [&](auto& self, const vector<int>& v) -> void {
// base case
int subn = v.size() + 1;
if (subn == 1) {
return;
}
if (subn == 2) {
push(v[0], 0);
push(v[0], 1);
return;
}
// find centroid
map<int, vector<edge> > T;
for (int i : v) {
T[U[i]].push_back(edge{V[i], i});
T[V[i]].push_back(edge{U[i], i});
}
map<int, int> subsize;
int centroid = -1;
auto dfs1 = [&](auto& self, int x, int pre) -> void {
subsize[x] = 1;
bool flag = true;
for (edge e : T[x]) {
if (e.t != pre) {
self(self, e.t, x);
subsize[x] += subsize[e.t];
flag = flag && (subsize[e.t] * 2 <= subn);
}
}
if (flag && subsize[x] * 2 >= subn) {
centroid = x;
}
};
dfs1(dfs1, U[v[0]], -1);
// coloring subtrees
map<int, int> depth;
depth[centroid] = 0;
vector<vector<int> > packv;
auto dfs2 = [&](auto& self, int x, int pre) -> void {
depth[x] = depth[pre] + 1;
for (edge e : T[x]) {
if (e.t != pre) {
packv.back().push_back(e.id);
self(self, e.t, x);
}
}
};
for (edge e : T[centroid]) {
packv.push_back({e.id});
dfs2(dfs2, e.t, centroid);
}
vector<vector<int> > groups = grouping(subn - 1, packv);
// orienting edges
for (int i = 0; i < int(groups.size()); i++) {
for (int j = 0; j < int(groups.size()); j++) {
for (int k : groups[j]) {
push(k, int(depth[U[k]] > depth[V[k]]) ^ int(i == j));
}
}
}
// recursion
for (const vector<int>& g : groups) {
self(self, g);
}
};
recur(recur, basev);
return f;
}
vector<bool> reachability(int N, int M, const vector<int>& U, const vector<int>& V, const vector<int>& f, int A) {
vector<vector<int> > G(N);
for (int i = 0; i < M; i++) {
if (f[i] == 0) {
G[U[i]].push_back(V[i]);
}
if (f[i] == 1) {
G[V[i]].push_back(U[i]);
}
}
vector<bool> vis(N, false);
auto dfs = [&](auto& self, int x) -> void {
vis[x] = true;
for (int i : G[x]) {
if (!vis[i]) {
self(self, i);
}
}
};
dfs(dfs, A);
return vis;
}
vector<int> topological_sort(int N, int M, const vector<int>& U, const vector<int>& V, const vector<int>& f) {
vector<vector<int> > G(N);
vector<int> deg(N);
for (int i = 0; i < M; i++) {
if (f[i] == 0) {
G[U[i]].push_back(V[i]);
deg[V[i]]++;
}
if (f[i] == 1) {
G[V[i]].push_back(U[i]);
deg[U[i]]++;
}
}
vector<int> st;
for (int i = 0; i < N; i++) {
if (deg[i] == 0) {
st.push_back(i);
}
}
vector<int> res(N, -1);
int cnt = 0;
while (!st.empty()) {
int u = st.back();
st.pop_back();
res[u] = cnt++;
for (int i : G[u]) {
deg[i]--;
if (deg[i] == 0) {
st.push_back(i);
}
}
}
return res;
}
void solve(int N, int M, vector<int> U, vector<int> V) {
// step #1. get "yes" response
vector<vector<int> > seq = make_sequence_tree(N, M, U, V);
int Z = seq.size();
vector<vector<int> > ord(Z);
for (int i = 0; i < Z; i++) {
ord[i] = topological_sort(N, M, U, V, seq[i]);
}
for (int i = 0; i < Z; i++) {
for (int j = 0; j < M; j++) {
if (seq[i][j] == -1) {
seq[i][j] = (ord[i][U[j]] < ord[i][V[j]] ? 0 : 1);
}
}
}
int pos = -1;
vector<int> tarseq, tarord;
for (int i = 0; i < Z; i++) {
bool subres = query(seq[i]);
if (subres) {
pos = i;
tarseq = seq[i];
tarord = ord[i];
break;
}
}
vector<int> tarinv(N);
for (int i = 0; i < N; i++) {
tarinv[tarord[i]] = i;
}
// step #2. find A with binary search
int la = 0, ra = N;
while (ra - la > 1) {
int m = (la + ra) / 2;
vector<int> f(M);
for (int i = 0; i < M; i++) {
f[i] = tarseq[i] ^ (tarord[tarseq[i] == 0 ? U[i] : V[i]] < m ? 1 : 0);
}
bool subres = query(f);
if (subres) {
la = m;
} else {
ra = m;
}
}
int A = tarinv[la];
// step #3. find B with binary search
vector<bool> valid(N, true);
for (int i = 0; i <= pos; i++) {
vector<bool> reach = reachability(N, M, U, V, seq[i], A);
for (int j = 0; j < N; j++) {
valid[j] = valid[j] && (i != pos ? !reach[j] : reach[j]);
}
}
vector<int> cand;
for (int i = 0; i < N; i++) {
if (valid[i]) {
cand.push_back(i);
}
}
sort(cand.begin(), cand.end(), [&](int a, int b) {
return tarord[a] < tarord[b];
});
int lb = 0, rb = cand.size();
while (rb - lb > 1) {
int m = (lb + rb) / 2;
int x = cand[m];
vector<int> f(M);
for (int i = 0; i < M; i++) {
f[i] = tarseq[i] ^ (tarord[tarseq[i] == 0 ? V[i] : U[i]] >= tarord[x] ? 1 : 0);
}
bool subres = query(f);
if (subres) {
rb = m;
} else {
lb = m;
}
}
int B = cand[lb];
answer(A, B);
}
