#include <algorithm>
#include <highway.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
#define maxN 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <ll, ll>
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int n, m;
int D[maxN];
int L[maxN];
vector <int> Lin, node;
vector <pii> Lv[maxN], E[maxN];
void dfs(int nd, int pr, int in)
{
node.pb(nd);
if(in != -1) {
Lin.pb(in);
L[nd] = L[pr]+1;
Lv[L[nd]].pb({nd, in});
}
for(auto i: E[nd]) {
if(i.ff == pr) continue;
dfs(i.ff, nd, i.ss);
}
}
void find_pair(int N, vector <int> U, vector <int> V, int A, int B)
{
m = U.size(), n = N;
for(int i = 0; i < m; i++) {
E[U[i]].pb({V[i], i});
E[V[i]].pb({U[i], i});
D[U[i]]++;
D[V[i]]++;
}
int ok = 1, x = 0;
for(int i = 0; i < n; i++) {
if(D[i] > 2) ok = 0;
if(D[i] == 1) x = i;
}
vector <int> arr;
for(int i = 0; i < m; i++) arr.pb(0);
int ans = ask(arr) / A;
if(ok == 0) {
dfs(0, -1, -1);
int l = 0, r = m-1, md, in = 0;
while(l <= r) {
md = (l+r)/2;
vector <int> arr;
for(int i = 0; i < m; i++) arr.pb(0);
for(int i = 0; i <= md; i++) arr[Lv[ans][i].ss] = 1;
int cur = ask(arr);
if(ans * A != cur) r = md-1, in = md;
else l = md+1;
}
answer(0, Lv[ans][in].ff);
}
else {
dfs(x, -1, -1);
int l = 0, r = m-1, md, in = 0;
while(l <= r) {
md = (l+r)/2;
vector <int> arr;
for(int i = 0; i < m; i++) arr.pb(0);
for(int i = 0; i <= md; i++) arr[Lin[i]] = 1;
int cur = ask(arr);
if(ans * A != cur) r = md-1, in = md;
else l = md+1;
}
answer(node[in], U[ans+in]);
}
}
