#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, K = 50, MAX_T = 2e5 + 5;
int n;
int h[MAX_N]; // Not id
int t;
int e1[MAX_T], e2[MAX_T]; // Not id
int id[MAX_N], rev_id[MAX_N];
vector<pii> upds[MAX_N]; // {time, node} and {0, -1}
set<int> adj[MAX_N]; // reused
vector<vector<int>> crit_adjs[MAX_N];
void update1(int u, int v, set<int>& s) { // one-way
if (s.count(v)) s.erase(v);
else s.insert(v);
}
void save(int u) {
vector<int> cur_adj(adj[u].begin(), adj[u].end());
crit_adjs[u].push_back(cur_adj);
}
void precomp() {
vector<pii> order;
for (int i = 0; i < n; i++) order.push_back({h[i], i});
sort(order.begin(), order.end());
for (int i = 0; i < n; i++) {
id[order[i].second] = i;
rev_id[i] = order[i].second;
}
for (int upd = 0; upd <= t; upd++) {
if (upd == 0) {
for (int u = 0; u < n; u++) {
upds[u].push_back({0, -1});
save(u);
}
continue;
}
int u = id[e1[upd]], v = id[e2[upd]];
update1(u, v, adj[u]);
update1(v, u, adj[v]);
upds[u].push_back({upd, v});
upds[v].push_back({upd, u});
if (((int) upds[u].size() - 1) % K == 0) save(u);
if (((int) upds[v].size() - 1) % K == 0) save(v);
}
}
void init(int tmp_n, int tmp_d, int tmp_h[]) {
n = tmp_n;
for (int i = 0; i < n; i++) h[i] = tmp_h[i];
}
void curseChanges(int tmp_t, int tmp_e1[], int tmp_e2[]) {
t = tmp_t;
for (int i = 1; i <= t; i++) {
e1[i] = tmp_e1[i - 1];
e2[i] = tmp_e2[i - 1];
}
precomp();
}
set<int> update2(int u, int upd) {
// First update with time <= upd
int hi = upper_bound(upds[u].begin(), upds[u].end(), make_pair(upd, (int) 1e9)) - upds[u].begin() - 1;
int lo = K * (hi / K);
set<int> cur_adj(crit_adjs[u][hi / K].begin(), crit_adjs[u][hi / K].end());
for (int i = lo + 1; i <= hi; i++)
update1(u, upds[u][i].second, cur_adj);
return cur_adj;
}
int question(int u, int v, int upd) {
u = id[u];
v = id[v];
set<int> u_adj(update2(u, upd));
set<int> v_adj(update2(v, upd));
int ans = 1e9;
auto u_it = u_adj.begin(), v_it = v_adj.begin();
while (u_it != u_adj.end() && v_it != v_adj.end()) {
int u_h = h[rev_id[*u_it]], v_h = h[rev_id[*v_it]];
ans = min(ans, abs(u_h - v_h));
if (u_h <= v_h) u_it++;
else v_it++;
}
return ans;
}
