#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
int n, m, a, b;
vvi adj;
vi dist, eu, ev, par, epar;
void dfs(int u, int p) {
if (u != p) dist[u] = dist[p] + 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n = N; m = U.size(); eu = U; ev = V;
adj.assign(n, vi()); for (int i = 0; i < m; i++) adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]);
dist.assign(n, 0);
dfs(0, 0);
par.assign(n, -1); epar.assign(n, -1); for (int i = 0; i < m; i++) {
if (dist[U[i]] < dist[V[i]]) {
par[V[i]] = U[i];
epar[V[i]] = i;
} else {
par[U[i]] = V[i];
epar[U[i]] = i;
}
}
ll base = ask(vi(m, 0));
int path_length = base / ll(A);
vi options; for (int i = 1; i < n; i++) if (dist[i] == path_length) options.push_back(i);
int lo = 0, hi = options.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi qn(m, 0); for (int i = lo; i <= mid; i++) qn[i] = 1;
ll ans = ask(qn);
if (ans == base) {
lo = mid + 1;
} else {
hi = mid;
}
}
// for (int j = 0; j < 50; ++j) {
// vector<int> w(M);
// for (int i = 0; i < M; ++i) {
// w[i] = 0;
// }
// ll toll = ask(w);
// }
answer(0, options[lo]);
}
