#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int M = 200'000;
vector<int> h(M);
int n, d;
vector<int> is_off(M);
void init(int N, int D, int H[]) {
n=N,d=D;
for(int i=0; i<n; ++i) h[i] = H[i];
}
struct Neigh {
int S = 5;
set<pair<int, int>> secik;
vector<vector<pair<int, int>>> save;
vector<pair<int, int>> changes;
vector<int> ztime;
void init() {
save.push_back({});
ztime.push_back(0);
changes.push_back({0,0});
}
void update(int x, int t) {
ztime.push_back(t);
if(secik.find({h[x], x})==secik.end()) {
changes.push_back({x,1});
secik.insert({h[x], x});
} else {
changes.push_back({x,-1});
secik.erase({h[x], x});
}
if((changes.size()-1)%S == 0) {
vector<pair<int, int>> reb;
for(auto x : secik) reb.push_back(x);
save.push_back(reb);
}
}
vector<int> getvec(int T) {
T = upper_bound(ztime.begin(), ztime.end(), T) - ztime.begin() - 1;
if(T%S==0) {
vector<int> ans;
for(auto[a,b] : save[T/S]) ans.push_back(a);
return ans;
}
vector<pair<int, int>> f = save[T/S];
vector<pair<int, int>> s;
int t1 = T/S + 1;
for(int i=t1; i<=T; ++i) {
if(changes[i].second==1) {
is_off[changes[i].first] = 0;
s.push_back({h[changes[i].first], changes[i].first});
} else is_off[changes[i].first] = 1;
}
sort(s.begin(), s.end());
vector<int> ans;
int i=0,j=0;
while(i<f.size() && j<s.size()) {
if(is_off[f[i].second]) {
++i;
continue;
}
if(is_off[s[j].second]) {
++j;
continue;
}
if(f[i] < s[j]) {
ans.push_back(f[i].first);
++i;
} else {
ans.push_back(s[j].first);
++j;
}
}
while(i<f.size()) {
if(!is_off[f[i].second]) ans.push_back(f[i].first);
++i;
}
while(j<s.size()) {
if(!is_off[s[j].second]) ans.push_back(s[j].first);
++j;
}
for(int i=t1; i<=T; ++i) {
is_off[changes[i].first] = 0;
}
return ans;
}
};
vector<Neigh> sasiad(M);
void curseChanges(int U, int A[], int B[]) {
for(int i=0; i<n; ++i) sasiad[i].init();
for(int t=0; t<U; ++t) {
sasiad[A[t]].update(B[t],t+1);
sasiad[B[t]].update(A[t],t+1);
}
}
int question(int X, int Y, int V) {
vector<int> v1 = sasiad[X].getvec(V);
// for(auto x : v1) cout << x << " "; cout << "\n";
// cout << "end\n"; exit(0);
vector<int> v2 = sasiad[Y].getvec(V);
// for(auto x : v2) cout << x << " "; cout << "\n";
if(v1.size()==0 || v2.size()==0) return 1e9;
int idx = 0;
int best = 1e9;
for(auto x : v1) {
while(idx < v2.size()-1 && v2[idx+1] < x) idx++;
best = min(best, abs(x - v2[idx]));
if(idx < v2.size() - 1) best = min(best, abs(x - v2[idx+1]));
}
return best;
}
