#include "island.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define eb emplace_back
#define allv(v) ((v).begin()),((v).end())
const int X = 250;
const int MAXN = 100010;
const int NDIVX = 405;
const int MAXM = 300010;
const int MX = 1 << 17;
int N, M;
vector<int> node[MAXN], ed[MAXN];
int uni[MAXN];
vector<int> idx[MAXN];
int mem[NDIVX][MAXN];
int bigidx[MAXN];
int seg[2 * MX];
int guni(int x) { return x == uni[x] ? x : guni(uni[x]); }
void mkseg(int idx, int l, int r) {
if(l == r) seg[idx] = ed[0][l];
else {
int m = (l + r) / 2;
mkseg(idx * 2, l, m);
mkseg(idx * 2 + 1, m + 1, r);
seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
}
}
int gseg(int idx, int l, int r, int x, int y) {
if(x <= l && r <= y) return seg[idx];
else if(r < x || y < l) return M;
int m = (l + r) / 2;
return min(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}
int gseg(int x, int y) { return gseg(1, 0, N - 2, x, y); }
void Init(int K, vector<int> F, vector<int> S, vector<int> E){
N = F.size();
M = S.size();
for(int i = 0; i < N; i++) {
uni[i] = i;
node[i].eb(i);
}
for(int i = M - 1; i >= 0; i--) {
S[i] = guni(S[i]);
E[i] = guni(E[i]);
if(S[i] == E[i]) continue;
if(node[S[i]].size() < node[E[i]].size()) swap(S[i], E[i]);
node[S[i]].insert(node[S[i]].end(), allv(node[E[i]]));
ed[S[i]].eb(i);
ed[S[i]].insert(ed[S[i]].end(), allv(ed[E[i]]));
uni[E[i]] = S[i];
}
for(int i = 0; i < N; i++) if(i == uni[i]) {
node[0] = node[i];
ed[0] = ed[i];
}
for(int i = 0; i < N; i++) idx[F[node[0][i]]].eb(i);
mkseg(1, 0, N - 2);
int cnt = 0;
for(int i = 0; i < K; i++) {
if(idx[i].size() > X) {
bigidx[i] = cnt++;
int mn = M;
for(int j = idx[i][0] + 1; j < N; j++) {
mn = min(mn, ed[0][j - 1]);
if(F[node[0][j]] == i) mn = M;
else mem[bigidx[i]][F[node[0][j]]] = max(mem[bigidx[i]][F[node[0][j]]], mn);
}
mn = M;
for(int j = idx[i].back() - 1; j >= 0; j--) {
mn = min(mn, ed[0][j]);
if(F[node[0][j]] == i) mn = M;
else mem[bigidx[i]][F[node[0][j]]] = max(mem[bigidx[i]][F[node[0][j]]], mn);
}
}
else bigidx[i] = -1;
}
}
int Separate(int A, int B){
if(bigidx[A] != -1) return mem[bigidx[A]][B] + 1;
if(bigidx[B] != -1) return mem[bigidx[B]][A] + 1;
int ans = 0;
int pa = 0, pb = 0;
while(pa < idx[A].size() && pb < idx[B].size()) {
if(idx[A][pa] < idx[B][pb]) {
if(pa == idx[A].size() - 1 || idx[A][pa + 1] > idx[B][pb])
ans = max(ans, gseg(idx[A][pa], idx[B][pb] - 1));
pa++;
}
else {
if(pb == idx[B].size() - 1 || idx[B][pb + 1] > idx[A][pa])
ans = max(ans, gseg(idx[B][pb], idx[A][pa] - 1));
pb++;
}
}
return ans + 1;
}
