#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 UnionFindPathCompression {
int n;
vector<int> uf;
UnionFindPathCompression(int n=0):n(n),uf(n){
for(int i=0;i<n;++i) uf[i]=i;
}
int find(int x){return uf[x] = x==uf[x]?x:find(uf[x]);}
void join(int x, int y){
if((x=find(x))==(y=find(y))) return;
uf[y]=x;
}
};
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);
}
vector<pair<int,int>> queries;
for(int finch=0;finch<K;++finch) if(pos[finch].size() >= GAP)
for(int i=finch+1;i<K;++i) queries.push_back({finch,i});
int Q = queries.size();
vector<int> lo(Q,0), hi(Q,M-1);
for(int iter=19;iter--;){
vector<vector<int>> mid(M);
for(auto i=0;i<Q;++i)
mid[(lo[i]+hi[i])/2].push_back(i);
UnionFind dsu(N);
for(int i=0;i<M;++i){
dsu.join(edges[i].first, edges[i].second, 0);
for(auto j:mid[i]){
int A = queries[j].first, B = queries[j].second;
if(pos[A].size() > pos[B].size()) swap(A,B);
int ok = 0;
for(auto i:pos[A]) dsu.join(pos[A][0], i, 1);
for(auto i:pos[B])
ok |= dsu.find(pos[A][0]) == dsu.find(i);
if(ok)
hi[j] = i;
else
lo[j] = i + 1;
dsu.rollback();
}
}
}
for(int i=0;i<Q;++i){
// cout << queries[i].first << ' ' << queries[i].second << ' ' << M - hi[i] << '\n';
memo[queries[i].first][queries[i].second] = max(memo[queries[i].first][queries[i].second], M - hi[i]);
}
}
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;
}
