// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#include "highway.h"
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
int n, m;
ii eg[MAXN];
vii adj[MAXN];
int a, b;
ll itoll;
vi w;
int dis[2][MAXN];
ii p[MAXN];
int lvl[MAXN];
int vis[MAXN];
bool back[MAXN];
void dfs(int u) {
vis[u] = 1;
for (auto [v, i] : adj[u]) {
if (v == p[u].FI) continue;
if (vis[v] == 1) {
back[i] = 1;
}
if (vis[v]) continue;
if (dis[0][v] >= dis[1][v]) continue;
p[v] = {u, i};
lvl[v] = lvl[u] + 1;
dfs(v);
}
vis[u] = 2;
}
void bfs(int s, int z) {
queue<int> q;
REP (i, 0, n) {
dis[z][i] = INF;
}
q.push(s);
dis[z][s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto [v, i] : adj[u]) {
if (mnto(dis[z][v], dis[z][u] + 1)) {
q.push(v);
}
}
}
}
void find_pair(int N, vi U, vi V, int A, int B) {
n = N, m = U.size();
a = A, b = B;
REP (i, 0, m) {
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
eg[i] = {U[i], V[i]};
}
w = vi(m, 0);
itoll = ask(w);
int sl = -1, tl;
{
int lo = 0, hi = m - 1, mid;
while (lo < hi) {
mid = lo + hi >> 1;
w = vi(m, 0);
REP (i, 0, mid + 1) {
w[i] = 1;
}
ll toll = ask(w);
if (toll != itoll) {
hi = mid;
} else {
lo = mid + 1;
}
}
tie(sl, tl) = eg[lo];
}
assert(sl != -1);
cerr << sl << ' ' << tl << '\n';
bfs(sl, 0); bfs(tl, 1);
int s = -1, t = -1;
REP (z, 0, 2) {
dfs(sl);
REP (i, 0, m) {
if (lvl[eg[i].FI] < lvl[eg[i].SE]) {
swap(eg[i].FI, eg[i].SE);
}
}
vi pot;
REP (i, 0, n) {
if (i == sl) continue;
if (dis[0][i] < dis[1][i]) {
pot.pb(i);
}
}
sort(ALL(pot), [&] (int l, int r) {
return lvl[l] < lvl[r];
});
{
int lo = -1, hi = pot.size() - 1, mid;
while (lo < hi) {
w = vi(m, 0);
int mid = lo + hi == -1 ? -1 : lo + hi >> 1;
REP (i, mid + 1, pot.size()) {
w[p[pot[i]].SE] = 1;
}
REP (i, 0, m) {
if (back[i]) {
w[i] = 1;
}
}
cerr << lo << ' ' << hi << ' ' << mid << '\n';
REP (i, 0, m) {
cerr << " " << w[i];
}
cerr << '\n';
ll toll = ask(w);
if (toll == itoll) {
hi = mid;
} else {
lo = mid + 1;
}
}
cerr << ' ' << hi << '\n';
if (hi == -1) {
s = sl;
} else {
s = eg[p[pot[hi]].SE].FI;
}
}
assert(s != -1);
memset(lvl, 0, sizeof lvl);
memset(back, 0, sizeof back);
memset(vis, 0, sizeof vis);
swap(s, t);
swap(sl, tl);
swap(dis[0], dis[1]);
}
answer(s, t);
cerr << s << ' ' << t << '\n';
}
