#include <bits/stdc++.h>
//#include "grader.cpp"
#include "highway.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define piii pair <int, pair <int, int> >
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) (x).back()
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
vector <pii> g[N];
ll base;
int ans[2], d[N], D[N];
vi w, lt;
bool gd(int n, int m, int x, ll base)
{
for (int i = 0; i <= x; i++)
w[i] = 0;
for (int i = x + 1; i < m; i++)
w[i] = 1;
return (ask(w) == base);
}
int getft(int n, int m)
{
for (int i = 0; i < m; i++)
w[i] = 1;
base = ask(w);
int l = 0;
int r = m - 1;
while (l < r)
{
int md = (l + r + 1) >> 1;
if (gd(n, m, md, base))
l = md;
else r = md - 1;
}
return l;
}
int getlst(vi lt, int m)
{
int l = 0;
int r = sz(lt) - 1;
while (l < r)
{
int md = (l + r) >> 1;
for (int i = 0; i < m; i++) w[i] = 1;
for (int i = 0; i <= md; i++)
w[lt[i]] = 0;
for (int i = md + 1; i < sz(lt); i++)
w[lt[i]] = 1;
if (ask(w) != base)
l = md + 1;
else r = md;
}
return l;
}
void dfs(int v, int pr)
{
if (pr == -1)
d[v] = 0;
else d[v] = d[pr] + 1;
for (auto u : g[v])
{
if (u.F == pr)
continue;
dfs(u.F, v);
}
}
void dfs_0(int v, int pr, int de)
{
D[v] = de;
for (auto u : g[v])
{
if (u.F == pr)
continue;
lt.pb(u.S);
dfs_0(u.F, v, de + 1);
}
}
void find_pair(int n, vi u, vi v, int a, int b)
{
int m = sz(u);
for (int i = 0; i < m; i++)
{
g[u[i]].pb({v[i], i});
g[v[i]].pb({u[i], i});
}
dfs(0, -1);
w.resize(m);
int ft = getft(n, m);
int upper, lower;
if (d[u[ft]] < d[v[ft]])
upper = u[ft], lower = v[ft];
else upper = v[ft], lower = u[ft];
lt.pb(ft);
dfs_0(upper, lower, 0);
int lst = getlst(lt, m);
// cerr << lst << el;
int U = u[lt[lst]];
int V = v[lt[lst]];
if (D[U] < D[V])
ans[0] = U;
else ans[0] = V;
lt.clear();
dfs_0(lower, upper, 0);
lst = getlst(lt, m);
U = u[lt[lst]];
V = v[lt[lst]];
if (D[U] < D[V])
ans[1] = U;
else ans[1] = V;
// cout << ans[0] << " " << ans[1] << el;
answer(ans[0], ans[1]);
}
/*int main()
{
srand(time(0));
cout.precision(3);
cout << fixed;
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// in("input.txt");
// out("output.txt");
}*/
/*
4 4
0110
0000
1101
1100
*/
