#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const int N=3e5+5;
const ll mod=1e9+7;
int n,m,k,a[N],u[N],v[N];
int par[N]; vector<int> g[N];
vector<int> gp[N]; // 소속되었던 그룹 번호들
map<int,int> mp[N];
int fi(int x)
{
if(par[x]==x) return x;
return par[x]=fi(par[x]);
}
void un(int x,int y,int t)
{
x=fi(x); y=fi(y);
if(g[x].size()<g[y].size()) swap(x,y);
par[y]=x;
for(auto &it : g[y]){
if(mp[x][a[it]]) continue;
gp[a[it]].push_back(x);
g[x].push_back(it);
//cout<<x<<" with "<<y<<" : "<<it<<" , "<<a[it]<<" , "<<x<<" , "<<t<<endl;
mp[x][a[it]]=t;
}
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
n=F.size(); m=S.size(); k=K;
for(int i=0;i<n;i++) a[i+1]=F[i]+1;
for(int i=0;i<m;i++) u[i+1]=S[i]+1,v[i+1]=E[i]+1;
for(int i=1;i<=n;i++){
par[i]=i;
gp[a[i]].push_back(i);
g[i].push_back(i);
mp[i][a[i]]=m+1;
}
for(int i=m;i>=1;i--){
if(fi(u[i])==fi(v[i])) continue;
un(u[i],v[i],i);
}
}
int Separate(int a,int b)
{
a++; b++;
int ans=1;
if(gp[a].size()>gp[b].size()) swap(a,b);
for(auto &g : gp[a]){
if(!mp[g][b]) continue;
else ans=max(ans,min(mp[g][a],mp[g][b]));
}
return ans;
}
