#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 9e4 + 100;
int N, M;
bool processed[mxn], mark[mxn];
int id[mxn], dep[mxn], sz[mxn];
vector<pair<int, int>> g[mxn];
vector<int> w;
int getSize(int cur, int P = -1) {
sz[cur] = !processed[cur];
for (auto to : g[cur]) {
if (to.first == P) continue;
dep[to.first] = dep[cur] + 1;
id[to.first] = to.second;
sz[cur] += getSize(to.first, cur);
}
return sz[cur];
}
void Erase(bool found) {
for (int i = 0; i < N; i++) {
if (mark[i] != found) processed[i] = 1;
}
}
void Set(int cur) {
if (!sz[cur]) return;
if (!processed[cur]) {
mark[cur] = 1;
w[id[cur]] = 1;
}
for (auto to : g[cur]) {
if (dep[to.first] < dep[cur]) continue;
Set(to.first);
}
}
void Fill(int cur, int x) {
for (auto to : g[cur]) {
if (dep[to.first] < dep[cur] || !x) continue;
if (sz[to.first] > x) {
Fill(to.first, x);
return;
}
x -= sz[to.first];
Set(to.first);
}
}
int Find(int fixed = 0) {
memset(processed, 0, sizeof(processed));
processed[fixed] = 1;
w.resize(M, 0);
for (int i = 0; i < M; i++) w[i] = 0;
int sz = N - 1;
long long sum = ask(w);
int times = log2(sz) + 2;
for (int i = 0; i < times; i++) {
memset(dep, 0, sizeof(dep));
memset(mark, 0, sizeof(mark));
getSize(fixed);
for (int j = 0; j < M; j++) w[j] = 0;
int amm = sz / 2;
if (amm == 0) break;
Fill(fixed, amm);
long long newSum = ask(w);
Erase(newSum != sum);
sz -= amm;
}
int ind;
for (int i = 0; i < N; i++) if (!processed[i]) ind = i;
return ind;
}
void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
N = _N;
M = U.size();
for (int i = 0; i < M; i++) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
int S = Find(0);
int T = Find(S);
answer(S, T);
}
