#include "island.h"
#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
using namespace std;
using pi = pair<int, int>;
const int MAXN = 400005;
struct disj{
int pa[MAXN];
void init(int n){
iota(pa, pa + n + 1, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
if(p < q) swap(p, q);
pa[q] = p; return 1;
}
}disj;
int N, piv;
vector<int> gph[MAXN];
vector<int> V[MAXN];
int din[MAXN], dout[MAXN], cst[MAXN];
int elem[20][MAXN];
void dfs(int x){
for(auto &i : gph[x]){
din[i] = ++piv;
elem[0][din[i]] = cst[x];
dfs(i);
dout[i] = ++piv;
elem[0][dout[i]] = cst[x];
}
}
bool cmp(int x, int y){ return din[x] < din[y]; }
int lg[MAXN];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
for(int i=1; i<MAXN; i++){
lg[i] = lg[i-1];
while((2 << lg[i]) <= i) lg[i]++;
}
N = sz(F);
disj.init(2 * N);
int cnt = N;
memset(cst, 0x3f, sizeof(cst));
for(int i=(int)S.size()-1; i>=0; i--){
int l = disj.find(S[i]);
int r = disj.find(E[i]);
if(disj.find(l) != disj.find(r)){
disj.uni(l, cnt);
disj.uni(r, cnt);
cst[cnt] = i + 1;
gph[cnt].push_back(l);
gph[cnt].push_back(r);
cnt++;
}
}
memset(elem, 0x3f, sizeof(elem));
dfs(cnt - 1);
for(int i=0; i<N; i++){
V[F[i]].push_back(i);
}
for(int i=0; i<K; i++) sort(V[i].begin(), V[i].end(), cmp);
for(int i=1; i<20; i++){
for(int j=1; j<=piv; j++){
elem[i][j] = elem[i-1][j];
if(j >= (1 << (i-1))) elem[i][j] = min(elem[i][j], elem[i-1][j - (1<<(i-1))]);
}
}
}
int QUERY(int x, int y){
int L = lg[y - x + 1];
return min(elem[L][y], elem[L][x + (1<<L) - 1]);
}
map<pi, int> mp;
int Separate(int A, int B){
if(sz(V[A]) > sz(V[B])) swap(A, B);
if(mp.find(pi(A, B)) != mp.end()) return mp[pi(A, B)];
int ret = 0;
for(auto &i : V[A]){
auto itr = upper_bound(V[B].begin(), V[B].end(), i, cmp);
if(itr != V[B].begin()){
ret = max(ret, QUERY(dout[*prev(itr)], din[i]));
}
if(itr != V[B].end()){
ret = max(ret, QUERY(din[i] + 1, din[*itr]));
}
}
mp[pi(A, B)] = mp[pi(B, A)] = ret;
return ret;
}
