#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int GAP = 500;
struct UnionFind {
int n,comp;
vector<int> uf,si,c;
UnionFind(int n=0):n(n),comp(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;comp--;
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;comp++;
}
}
} UF[605];
vector<pair<int,int>> edges;
vector<int> F;
int M;
void Init(int K, vector<int> F, vector<int> S, vector<int> E){
M = S.size();
edges.resize(M);
for(int i=0;i<M;++i)
edges[i] = make_pair(S[i], E[i]);
reverse(edges.begin(), edges.end());
UnionFind cur(K);
::F = F;
for(int i=0;i<M;++i){
if(i%GAP==0) UF[i/GAP] = cur;
cur.join(F[edges[i].first], F[edges[i].second], 0);
}
}
int Separate(int A, int B){
int bucket = 0, start = 0, ans = 0;
for(int i=0;i<M;i+=GAP){
if(UF[i/GAP].find(A) == UF[i/GAP].find(B))
break;
start = i, bucket = i/GAP;
}
for(int i=start;i<start+GAP && i<M; ++i){
// cout << "Joining " << F[edges[i].first] << ' ' << F[edges[i].second] << '\n';
UF[bucket].join(F[edges[i].first], F[edges[i].second]);
if(UF[bucket].find(A) == UF[bucket].find(B)){
ans = M - i;
break;
}
}
UF[bucket].rollback();
return ans;
}
