#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e9
#define nl '\n'
const int N = 1e5+1, l = 4347, k = 47;
int h[N], a[2*N], b[2*N];
unordered_map<int,int> g[N];
vector<int> sg[k][N];
void init(int n, int D, int H[]){
for(int i = 0; i < n; i++) h[i] = H[i];
}
void curseChanges(int u, int A[], int B[]){
unordered_map<int,int> cg[N];
for(int i = 1; i <= u; i++){
a[i] = A[i-1];
b[i] = B[i-1];
int x = a[i], y = b[i];
cg[x][y]++;
cg[y][x]++;
if(i % l == 0){
int div = i/l;
for(int j = 0; j < N; j++){
sg[div][j].reserve(cg[j].size());
for(auto &[z, c] : cg[j]){
if(c % 2) sg[div][j].push_back(z);
}
}
}
}
}
int question(int p, int q, int v){
int div = v/l;
auto &cg = sg[div];
for(int &x : cg[p]) g[p][x]++;
for(int &x : cg[q]) g[q][x]++;
for(int i = div * l + 1; i <= v; i++){
int x = a[i], y = b[i];
if(x == p or x == q) g[x][y]++;
if(y == p or y == q) g[y][x]++;
}
vector<int> v1, v2;
for(auto &[x, c] : g[p]){
if(c % 2) v1.push_back(h[x]);
}
for(auto &[x, c] : g[q]){
if(c % 2) v2.push_back(h[x]);
}
g[p].clear();
g[q].clear();
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int s1 = v1.size(), s2 = v2.size();
int ans = inf;
for(int i = 0, j = -1; i < s1; i++){
while(j+1 < s2 and v2[j+1] <= v1[i]) j++;
ans = min(ans, min(j >= 0 ? v1[i] - v2[j] : inf, j+1 < s2 ? v2[j+1] - v1[i] : inf));
}
return ans;
}
