//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; }