//ChatGPT code to check whats wrong
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 200000;
int n, d;
int h[MAXN];
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 {
static const int S = 50;
vector<int> curr; // aktualni sąsiedzi (indeksy)
vector<vector<int>> snap; // snapshoty (wysokości posortowane)
vector<pair<int,int>> changes; // (node, +1/-1)
vector<int> ztime; // czas zmiany
void init() {
curr.clear();
snap.clear();
changes.clear();
ztime.clear();
snap.push_back({});
changes.push_back({0,0});
ztime.push_back(0);
}
void toggle(int x) {
for(int i=0;i<(int)curr.size();i++) {
if(curr[i]==x) {
curr[i]=curr.back();
curr.pop_back();
return;
}
}
curr.push_back(x);
}
void make_snap() {
vector<int> v;
v.reserve(curr.size());
for(int x: curr) v.push_back(h[x]);
sort(v.begin(), v.end());
snap.push_back(v);
}
void update(int x, int t) {
ztime.push_back(t);
bool found=false;
for(int y: curr) if(y==x) { found=true; break; }
if(found) {
changes.push_back({x,-1});
} else {
changes.push_back({x,1});
}
toggle(x);
if((int)changes.size()%S==0) make_snap();
}
void getvec(int T, vector<int>& out) {
int id = upper_bound(ztime.begin(), ztime.end(), T) - ztime.begin() - 1;
int block = id / S;
out = snap[block]; // copy heights snapshot
// replay
int start = block*S + 1;
vector<int> add;
vector<int> rem;
add.reserve(S);
rem.reserve(S);
for(int i=start;i<=id;i++) {
if(changes[i].second==1) add.push_back(h[changes[i].first]);
else rem.push_back(h[changes[i].first]);
}
if(add.empty() && rem.empty()) return;
sort(add.begin(), add.end());
sort(rem.begin(), rem.end());
// merge add
vector<int> tmp;
tmp.reserve(out.size()+add.size());
merge(out.begin(), out.end(), add.begin(), add.end(), back_inserter(tmp));
// remove rem
out.clear();
int i=0,j=0;
while(i<(int)tmp.size()) {
if(j<(int)rem.size() && tmp[i]==rem[j]) {
i++; j++;
} else {
out.push_back(tmp[i]);
i++;
}
}
}
};
Neigh sasiad[MAXN];
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) {
static vector<int> v1, v2;
sasiad[X].getvec(V, v1);
sasiad[Y].getvec(V, v2);
if(v1.empty() || v2.empty()) return 1e9;
int j=0;
int best = 1e9;
for(int x: v1) {
while(j+1<(int)v2.size() && v2[j+1] <= x) j++;
best = min(best, abs(x - v2[j]));
if(j+1<(int)v2.size())
best = min(best, abs(x - v2[j+1]));
}
return best;
}
