#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); int best; 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<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<int> reb; for(auto[a,x] : secik) reb.push_back(a); save.push_back(reb); } } void getvec(int T, vector<int> &res) { T = upper_bound(ztime.begin(), ztime.end(), T) - ztime.begin() - 1; res = save[T/S]; if(T%S==0) return; int t1 = T/S + 1; vector<int> s; for(int i=t1; i<=T; ++i) { if(changes[i].second==1) { is_off[changes[i].first] = 0; s.push_back(changes[i].first); } else is_off[changes[i].first] = 1; } sort(s.begin(), s.end(), [&](int i, int j) { return h[i] < h[j]; }); vector<int> ans; int i=0,j=0; while(i<res.size() && j<s.size()) { if(h[res[i]] < h[s[j]]) { ans.push_back(res[i]); ++i; } else { ans.push_back(s[j]); ++j; } } while(i<res.size()) { ans.push_back(res[i]); ++i; } while(j<s.size()) { ans.push_back(s[j]); ++j; } res.clear(); for(auto x : ans) if(!is_off[x]) res.push_back(h[x]); for(int i=t1; i<=T; ++i) { is_off[changes[i].first] = 0; } } }; 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) { static vector<int> v1, v2; sasiad[X].getvec(V, v1); sasiad[Y].getvec(V, v2); 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; }