#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 300000;
const int GAP = 500;
struct UnionFind {
int n;
vector<int> uf,si,c;
UnionFind(int n=0):n(n),uf(n),si(n,1){
for(int i=0;i<n;++i)
uf[i]=i;
}
int find(int x){return x==uf[x]?x:find(uf[x]);}
bool join(int x, int y, bool keep_track = 1){
if((x=find(x))==(y=find(y))) return false;
if(si[x]<si[y]) swap(x,y);
si[x]+=si[y];uf[y]=x;
if(keep_track) c.push_back(y);
return true;
}
void rollback(){
while(c.size()){
int x=c.back(); c.pop_back();
si[uf[x]]-=si[x];uf[x]=x;;
}
}
} UF[603];
struct UnionFindFinches{
int n;
vector<int> si,uf;
vector<vector<pair<int,int>>> who;
vector<vector<int>> adj;
UnionFindFinches(int n=0):n(n),si(n,1),uf(n),who(n),adj(n){
for(int i=0;i<n;++i) uf[i]=i;
for(int i=0;i<n;++i) who[i].push_back({i,-1});
}
int find(int x){return x==uf[x]?x:find(uf[x]);}
void join(int x, int y, int time, bool merge){
if((x=find(x))==(y=find(y))) return;
if(!merge){
if(si[x]<si[y]) swap(x,y);
si[x]+=si[y];
}
uf[y]=x;
if(merge){
function<void(int)> dfs = [&](int y){
for(auto i:who[y])
who[x].push_back({i.first, time});
for(auto i:adj[y])
dfs(i);
who[y].clear();
si[y] = 0;
adj[y].clear();
};
dfs(y);
}
else
adj[x].push_back(y);
}
~UnionFindFinches(){}
};
vector<pair<int,int>> edges;
vector<int> pos[100005];
int M, N;
map<int,int> memo[100005];
void Init(int K, vector<int> F, vector<int> S, vector<int> E){
N = F.size();
M = S.size();
edges.resize(M);
for(int i=0;i<N;++i) memo[i].clear();
for(int i=0;i<K;++i) pos[i].clear();
for(int i=0;i<M;++i) edges[M-i-1] = {S[i], E[i]};
for(int i=0;i<(int)F.size();++i)
pos[F[i]].push_back(i);
UnionFind cur(N);
for(int i=0;i<M;++i){
if(i%GAP==0) UF[i/GAP] = cur;
cur.join(edges[i].first, edges[i].second, 0);
}
for(int finch=0;finch<K;++finch) if(pos[finch].size() >= GAP){
UnionFindFinches dsu(N);
for(auto i:pos[finch]) dsu.join(pos[finch][0], i, -1, 1);
for(int i=0;i<M;++i){
int x, y; tie(x,y) = edges[i];
if(F[x] == finch && F[y] == finch) continue;
if(F[y] == finch) swap(x,y);
dsu.join(x,y,i, F[x] == finch);
}
for(auto i:dsu.who[pos[finch][0]]){
memo[finch][F[i.first]] = max(memo[finch][F[i.first]], M - i.second);
}
}
}
int Separate(int A, int B){
if(A>B) swap(A,B);
if(memo[A].count(B)) return memo[A][B];
int bucket = 0, ans = -1;
int lo = 0, hi = (M-1)/GAP;
while(lo<hi){
int b = (lo + hi + 1)/2;
for(auto i:pos[A]) UF[b].join(pos[A][0], i, 1);
for(auto i:pos[B]) UF[b].join(pos[B][0], i, 1);
if(UF[b].find(pos[A][0]) == UF[b].find(pos[B][0])){
hi = b - 1;
}
else{
lo = b;
}
UF[b].rollback();
}
bucket = lo;
for(auto i:pos[A]) UF[bucket].join(pos[A][0], i, 1);
for(auto i:pos[B]) UF[bucket].join(pos[B][0], i, 1);
int start = bucket * GAP;
for(int i=start;i<=start+GAP && i<M; ++i){
UF[bucket].join(edges[i].first, edges[i].second, 1);
if(UF[bucket].find(pos[A][0]) == UF[bucket].find(pos[B][0])){
ans = M - i;
break;
}
}
UF[bucket].rollback();
return memo[A][B] = ans;
}
