#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 1.3e5 + 5;
ll len;
vector<pair<int, int>> adj[SIZE], all[2];
vector<int> e;
int g[SIZE];
bool is[SIZE];
int cal(int s, int M) {
int sz = all[s].size();
int l = 0, r = sz - 1;
while (l < r) {
int mid = (l + r) / 2;
FOR (i, 0, M - 1) e[i] = !is[i];
FOR (i, mid + 1, sz - 1) e[all[s][i].S] = 1;
if (ask(e) == len) r = mid;
else l = mid + 1;
}
return all[s][l].F;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
e.resize(M, 0);
FOR (i, 0, M - 1) {
adj[U[i]].pb(V[i], i);
adj[V[i]].pb(U[i], i);
}
len = ask(e);
int l = 0, r = M - 1;
while (l < r) {
int mid = (l + r) / 2;
fill(e.begin(), e.end(), 0);
fill(e.begin(), e.begin() + mid + 1, 1);
if (ask(e) == len) l = mid + 1;
else r = mid;
}
queue<int> q;
is[l] = 1;
fill(g, g + N, -1);
q.push(U[l]), g[U[l]] = 0, all[0].pb(U[l], -1);
q.push(V[l]), g[V[l]] = 1, all[1].pb(V[l], -1);
while (q.size()) {
int pos = q.front();
q.pop();
for (auto [np, id] : adj[pos]) if (g[np] == -1) {
g[np] = g[pos];
is[id] = 1;
all[g[pos]].pb(np, id);
q.push(np);
}
}
answer(cal(0, M), cal(1, M));
}
