#include "island.h"
int M;
struct nd
{
int f_par;
int s_par;
int tm;
int get(int t)
{
if(t >= tm) return s_par;
else return f_par;
}
};
nd uf[101010];
int rnk[101010];
int fnd(int x, int t)
{
int par = uf[x].get(t);
if(x == par) return x;
else return fnd(par, t);
}
void uni(int x, int y, int t)
{
x = fnd(x, t);
y = fnd(y, t);
if(x == y) return;
else
{
if(rnk[x] == rnk[y])
{
++rnk[x];
uf[y].s_par = x;
uf[y].tm = t;
}
else if(rnk[x] > rnk[y])
{
uf[y].s_par = x;
uf[y].tm = t;
}
else
{
uf[x].s_par = y;
uf[x].tm = t;
}
}
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
int N = F.size(); M = S.size();
for(int i = 0; i < N; ++i)
{
uf[i].f_par = i;
uf[i].s_par = -1;
uf[i].tm = M + 1;
}
for(int i = 1; i <= M; ++i)
{
uni(F[S[M - i]], F[E[M - i]], i);
}
}
int Separate(int A, int B){
int s = 0, t = M;
while(s + 1 < t)
{
int mid = (s + t) >> 1;
if(fnd(A, mid) == fnd(B, mid)) t = mid;
else s = mid;
}
return M - s;
}
