// 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;
ii p[MAXN];
int dis[MAXN], comp[MAXN];
bool back[MAXN];
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';
queue<int> q;
memset(comp, -1, sizeof comp);
REP (i, 0, n) {
dis[i] = INF;
}
dis[sl] = 0;
comp[sl] = sl;
q.push(sl);
dis[tl] = 0;
comp[tl] = tl;
q.push(tl);
while (!q.empty()) {
int u = q.front(); q.pop();
cerr << u << '\n';
for (auto [v, i] : adj[u]) {
if (mnto(dis[v], dis[u] + 1)) {
cerr << ' ' << v << '\n';
q.push(v);
p[v] = {u, i};
comp[v] = comp[u];
} else if (dis[v] == dis[u] + 1) {
back[i] = 1;
}
}
}
REP (i, 0, m) {
if (dis[eg[i].FI] < dis[eg[i].SE]) {
swap(eg[i].FI, eg[i].SE);
}
}
int s = -1, t = -1;
REP (z, 0, 2) {
vi pot;
REP (i, 0, n) {
if (i != sl && comp[i] == sl) {
pot.pb(i);
}
}
sort(ALL(pot), [&] (int l, int r) {
return dis[l] < dis[r];
});
cerr << sl << '\n';
for (int i : pot) {
cerr << " " << i;
}
cerr << '\n';
{
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;
}
}
if (hi == -1) {
s = sl;
} else {
cerr << " !" << p[pot[hi]].FI << '\n';
s = eg[p[pot[hi]].SE].FI;
}
cerr << ' ' << hi << ' ' << s << '\n';
}
assert(s != -1);
swap(s, t);
swap(sl, tl);
}
answer(s, t);
cerr << s << ' ' << t << '\n';
}
