// ~ Be Name Khoda ~ //
#include "highway.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
vector <int> tok, adj[maxn5], v, u, ver, ed;
ll len;
int m, q[maxn5], par[maxn5];
ll pas[maxn5];
bool mark[maxn5], good[maxn5];
void bfs(int rt){
par[rt] = -1;
memset(mark, false, sizeof mark);
int l = 0, r = 1;
q[0] = rt;
mark[rt] = true;
while(l < r){
int a = q[l++];
for(auto id : adj[a]){
int b = u[id] == a ? v[id] : u[id];
if(mark[b])
continue;
//cout << "here " << a << ' ' << b << ' ' << id << endl;
good[id] = true;
mark[b] = true;
q[r++] = b;
par[b] = a;
}
}
}
void dfs(int v){
//cout << v << ' ' << par[v] << endl;
for(auto id : adj[v]) if(good[id]){
int u = (::u[id]) == v ? (::v[id]) : (::u[id]);
if(u == par[v])
continue;
//cout << "in " << v << ' ' << u << ' ' << id << endl;
dfs(u);
ver.pb(u);
ed.pb(id);
}
}
ll get(int id){
if(pas[id] == -1){
fill(all(tok), 1);
for(auto u : ed)
tok[u] = false;
for(int i = 0; i <= id; i++)
tok[ed[i]] = true;
pas[id] = ask(tok);
}
return pas[id];
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
memset(pas, -1, sizeof pas);
u = U;
v = V;
m = u.size();
for(int i = 0; i < m; i++){
adj[u[i]].pb(i);
adj[v[i]].pb(i);
}
int lo = -1, hi = n;
tok.resize(m);
fill(all(tok), 0);
len = ask(tok) / a;
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
fill(all(tok), 0);
for(int i = 0; i <= mid; i++)
for(auto id : adj[i])
tok[id] = 1;
ll cost = ask(tok);
if(cost == len * a)
lo = mid;
else
hi = mid;
}
assert(hi < n);
hi = 0; // pay attention, it've changed!!!!!!!!!!!!!!!!!!!
par[hi] = -1;
bfs(hi);
//return;
dfs(hi);
/*
for(int i = 0; i < n - 1; i++)
cout << ed[i] << ' ' << ver[i] << endl;
//*/
//cout << "its " << hi << endl;
lo = -1; hi = n - 1;
ll x;
int lim = 60000;
if(false && n > lim + 5){
x = get(lim);
if(x == len * a){
lo = lim;
hi = n - 1;
}
else{
lo = -1;
hi = lim;
}
}
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(get(mid) == len * a)
lo = mid;
else
hi = mid;
}
int s = ver[hi];
answer(s, 0);
return;
//cout << "here " << lo << ' ' << hi << ' ' << s << endl;
if(false && n > lim + 5){
if(x == len * b){
hi = lim;
lo = -1;
}
else{
lo = lim;
hi = n - 1;
}
}
else{
lo = -1;
hi = n - 1;
}
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
//cout << mid << ' ' << get(mid) << ' ' << len << ' ' << a << ' ' << b << endl;
if(get(mid) == len * b)
hi = mid;
else
lo = mid;
}
int v = s;
bool re = false;
while(v != -1){
if(v == ver[hi])
re = true;
v = par[v];
}
int t;
if(re)
t = par[ver[hi]];
else
t = ver[hi];
//cout << re << ' ' << hi << ' ' << lo << ' ' << t << endl;
answer(s, t);
return;
}
