#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define pii pair<int,int>
#define SZ 262144
int Col[101000], n, m, UF[101000], par[101000][20], Mx[101000][20], Dep[101000], Num[101000], Ed[101000], cnt, D[101000], vis[101000], Fnum[101000], pL[101000], P[101000];
vector<int>E[101000], L[101000], FF[101000], Fre, Ch[101000];
int DD[1260][100010], TH = 80, ReNum[101000];
int Find(int a) {
if (a == UF[a])return a;
return UF[a] = Find(UF[a]);
}
void Add_Edge(int a, int b, int c) {
E[a].push_back(b);
E[b].push_back(a);
L[a].push_back(c);
L[b].push_back(c);
}
void DFS(int a, int pp) {
Num[a] = ++cnt;
ReNum[cnt] = a;
par[a][0] = pp;
P[a] = pp;
for (int i = 0; i < 18; i++) {
par[a][i + 1] = par[par[a][i]][i];
Mx[a][i + 1] = max(Mx[par[a][i]][i], Mx[a][i]);
}
for (int i = 0; i < E[a].size(); i++) {
int x = E[a][i];
if (x == pp)continue;
Mx[x][0] = L[a][i];
pL[x] = L[a][i];
Dep[x] = Dep[a] + 1;
Ch[a].push_back(x);
DFS(x, a);
}
Ed[a] = cnt;
}
void Do1(int a) {
int i;
for (i = n; i > 1; i--) {
int a = ReNum[i];
D[P[a]] = min(D[P[a]], max(D[a], pL[a]));
}
}
void Do2(int a) {
int i;
for (i = 2; i <= n; i++) {
int a = ReNum[i];
D[a] = min(D[a], max(D[P[a]], pL[a]));
}
}
void Init(int K, std::vector<int> F, std::vector<int> A, std::vector<int> B) {
int i, j;
n = F.size(), m = A.size();
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for (i = 1; i <= n; i++) {
UF[i] = i;
Col[i] = F[i - 1] + 1;
FF[Col[i]].push_back(i);
}
for (i = 0; i < m; i++) {
int a = A[i] + 1, b = B[i] + 1;
if (Find(a) != Find(b)) {
UF[Find(a)] = Find(b);
Add_Edge(a, b, i + 1);
}
}
DFS(1, 0);
for (i = 1; i <= n; i++) {
if (FF[i].size() >= TH) {
Fre.push_back(i);
for (j = 1; j <= n; j++) {
D[j] = 1e9;
vis[j] = 0;
}
for (auto &x : FF[i]) {
D[x] = 0;
}
Do1(1);
Do2(1);
int cur = Fre.size() - 1;
Fnum[i] = cur;
for (j = 1; j <= K; j++) DD[cur][j] = 1e9;
for (j = 1; j <= n; j++)DD[cur][Col[j]] = min(DD[cur][Col[j]], D[j]);
}
}
for (i = 1; i <= n; i++)vis[i] = 0;
}
int Up(int a, int d) {
int i = 0;
while (d) {
if (d & 1)a = par[a][i];
d >>= 1; i++;
}
return a;
}
int LCA(int a, int b) {
if (Dep[a] < Dep[b])return LCA(b, a);
int d = Dep[a] - Dep[b], i;
a = Up(a, d);
for (i = 17; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
if (a != b)a = par[a][0];
return a;
}
vector<int>G[1010], GL[1010];
int NN[101000];
int UpMax(int a, int d) {
int r = 0, i = 0;
while (d) {
if (d & 1) {
r = max(r, Mx[a][i]);
a = par[a][i];
}
d >>= 1; i++;
}
return r;
}
int Dist(int a, int b) {
int d = Dep[a] - Dep[b];
int l = UpMax(a, d);
return l;
}
void Add(int a, int b, int l) {
G[a].push_back(b);
G[b].push_back(a);
GL[a].push_back(l);
GL[b].push_back(l);
}
int st[10100];
int T[10100], vv[101000];
void Do3(int a, int pp) {
for (int i = 0; i < G[a].size(); i++) {
int x = G[a][i], l = GL[a][i];
if (x == pp)continue;
Do3(x, a);
D[a] = min(D[a], max(D[x], l));
}
}
void Do4(int a, int pp) {
for (int i = 0; i < G[a].size(); i++) {
int x = G[a][i], l = GL[a][i];
if (x == pp)continue;
D[x] = min(D[x], max(D[a], l));
Do4(x, a);
}
}
int Separate(int A, int B) {
A++, B++;
if (FF[A].size() >= TH)return m + 1 - DD[Fnum[A]][B];
if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
int cnt = 0;
for (auto &t : FF[A])T[cnt++] = Num[t];
for (auto &t : FF[B])T[cnt++] = Num[t];
sort(T, T + cnt);
for (int i = 0; i < cnt; i++)vv[T[i]] = 1;
int tc = cnt;
for (int i = 1; i < tc; i++) {
int a = Num[LCA(ReNum[T[i - 1]], ReNum[T[i]])];
if (!vv[a]) {
vv[a] = 1;
T[cnt++] = a;
}
}
sort(T, T + cnt);
for (int i = 0; i < cnt; i++) {
vv[T[i]] = 0;
NN[ReNum[T[i]]] = i + 1;
}
int top = 0;
for (int i = 0; i < cnt; i++) {
int a = ReNum[T[i]];
while (top && (Num[a] < Num[st[top]] || Ed[st[top]] < Num[a])) top--;
if (top) {
Add(NN[a], NN[st[top]], Dist(a,st[top]));
}
st[++top] = a;
}
for (int i = 1; i <= cnt; i++) D[i] = 1e9;
for (int i = 0; i < cnt; i++) {
int a = ReNum[T[i]];
if (Col[a] == A) D[i + 1] = 0;
}
Do3(1, 0);
Do4(1, 0);
int res = 1e9;
for (int i = 0; i < cnt; i++) {
int a = ReNum[T[i]];
if (Col[a] == B) {
res = min(res, D[i + 1]);
}
}
for (int i = 1; i <= cnt; i++) {
G[i].clear();
GL[i].clear();
}
return m + 1 - res;
}
