Description

【题意】
给定长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$ 。
一次操作能选出部分 $i(1 \le i \le n)$ ，执行 $a_i=b_{a_i}$，
求最小的操作次数使得 $a$ 单调不降。

【输入格式】
一行一个整数 $t$ ( $ 1\le t\le 10^4 $ )，表示有 $t$ 组数据。
每组数据：
第一行两个整数 $ n $ 和 $ m $ ( $ 1\leq n \leq 10^6 $ , $ 1 \leq m \leq 10^6 $ ) 。
第二行 $ n $ 个整数 $a_i$ ( $ 1 \leq a_i \leq m $ ) 。
第三行 $ m $ 个整数 $b_i$ ( $ 1 \leq b_i \leq m $ ) 。
所有测试数据的 $ n $ 总和不超过$ 10^6 $ ， $ m $ 总和不超过 $ 10^6 $ .

【输出格式】
每组数据输出一行一个整数，表示最少的操作次数。若无解，输出-1。

【样例输入】
3
5 8
1 6 3 7 1
2 3 5 8 7 1 5 6
3 3
1 3 2
2 1 3
10 10
2 8 5 4 8 4 1 5 10 10
6 7 2 6 3 4 1 1 3 5

【样例输出】
3
-1
3

【提示】
In the first case, the initial array $ a_1, \ldots, a_n $ is $ [1, 6, 3, 7, 1] $ . You can choose $ S $ as follows:
- first trick: $ S = [2, 4, 5] $ , $ a = [1, 1, 3, 5, 2] $ ;
- second trick: $ S = [5] $ , $ a = [1, 1, 3, 5, 3] $ ;
- third trick: $ S = [5] $ , $ a = [1, 1, 3, 5, 5] $ .
 So it is possible to make $ a_1, \ldots, a_n $ non-decreasing using $ 3 $ tricks. It can be shown that this is the minimum possible amount of tricks.In the second case, it is impossible to make $ a_1, \ldots, a_n $ non-decreasing.

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10, inf=1e9;
int a[N], b[N], dep[N], fa[N], del[N], id[N], tsp, dfn[N]; 
int siz[N], n, m; vector<int> G[N];
int findfa(int x) {return (fa[x]==x)? fa[x]: fa[x]=findfa(fa[x]);}
bool pd1(int x, int y){
    int tx=findfa(x), ty=findfa(y); 
    if(tx!=ty) {fa[tx]=ty; return 0;}
    else return 1;
}
void dfs(int x){
    dfn[x]=++tsp; siz[x]=1;
    for(int y: G[x]){
        dep[y]=dep[x]+1;
        id[y]=id[x];
        dfs(y);
        siz[x]+=siz[y];
    }
}
bool pd2(int x, int y){   
    return ((dfn[x]>=dfn[y]) && (dfn[x]<=dfn[y]+siz[y]-1)); //x在y的子树内
}
int query(int x, int y){
    if(x==y) return 0;
    if(id[x]!=id[y]) return inf;
    int res=inf;
    if(pd2(x, y)) res=min(res, dep[x]-dep[y]); //x是y的子节点
    if(pd2(del[id[y]], y)) res=min(res, dep[del[id[y]]]-dep[y]+dep[x]+1); 
    //通过那条断的边走到环上的y，答案为环上的路径加x到环上那个节点的路径加短边
    return res;
}
bool check(int x){
    int i, w;
    for(i=1, w=1; i<=n, w<=m;){
        if(query(a[i], w)<=x) i++;
        else w++;
    }
    return i>n;
}
int main(){
    freopen("a.in", "r", stdin);
    int T; scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i=1; i<=m; i++){
            G[i].clear(); dep[i]=0; fa[i]=i;
            del[i]=0; id[i]=0; del[0]=0; dfn[i]=0;
        }
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=m; i++){
            scanf("%d", &b[i]);
            if(pd1(b[i], i)==0) G[b[i]].push_back(i);
            else del[i]=b[i]; //有环，断这条边
        }
        tsp=0; 
        for(int i=1; i<=m; i++) 
            if(del[i]) id[i]=i, dfs(i);
        int l=0, r=m, p=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)) r=mid-1, p=mid;
            else l=mid+1;
        }
        printf("%d\n", p);
    }
    return 0;
}