#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int NS = (int)2e5 + 4;
int lca[NS][24], pr[NS];
int n, m, ncnt, k;
vector<int> gr[NS], way[NS];
int euler[NS], en, tim[NS], dep[NS];
int eback[NS];
int fd(int x){
return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
int n = F.size(), m = S.size(), k = K;
for(int i = 0; i < NS; ++i){
pr[i] = i;
}
ncnt = n;
for(int i = m - 1; i >= 0; --i){
int x = S[i], y = E[i];
int px = fd(x), py = fd(y);
if(px == py){
continue;
}
pr[px] = pr[py] = ncnt;
lca[px][0] = lca[py][0] = ncnt;
way[ncnt] = {px, py};
tim[ncnt] = i;
++ncnt;
}
for(int j = 1; j < 20; ++j){
for(int i = 0; i < ncnt; ++i){
lca[i][j] = lca[lca[i][j - 1]][j - 1];
}
}
auto dfs = [&](auto&&self, int x)->void{
euler[x] = ++en;
eback[en] = x;
for(auto&nxt:way[x]){
dep[nxt] = dep[x] + 1;
self(self, nxt);
}
};
dfs(dfs, ncnt - 1);
for(int i = 0; i < n; ++i){
gr[F[i]].push_back(euler[i]);
}
for(int i = 0; i < k; ++i){
sort(gr[i].begin(), gr[i].end());
}
}
int gettime(int x, int y){
// cout << "FIND " << x << ' ' << y << endl;
if(dep[x] > dep[y]){
swap(x, y);
}
for(int i = 19; i >= 0; --i){
if(dep[y] - (1 << i) >= dep[x]){
y = lca[y][i];
}
}
if(x == y) return tim[x];
for(int i = 19; i >= 0; --i){
if(lca[x][i] != lca[y][i]){
x = lca[x][i];
y = lca[y][i];
}
}
return tim[lca[x][0]];
}
map<pair<int, int>, int> save;
int Separate(int A, int B){
int a = A, b = B;
if(a > b){
swap(a, b);
}
auto it = save.find(make_pair(a, b));
if(it != save.end()){
return it->second;
}
int ans = 0;
if((int)gr[A].size() > (int)gr[B].size()) swap(A, B);
for(int i = 0; i < (int)gr[A].size(); ++i){
int pos = lower_bound(gr[B].begin(), gr[B].end(), gr[A][i]) - gr[B].begin();
if(pos < (int)gr[B].size()){
ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
}
if(pos){
--pos;
ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
}
}
save[{a, b}] = ans + 1;
return ans + 1;
}
