C - 替换

题目背景

So are you gonna die today or make it out alive

You gotta conquer the monster in your head and then you'll fly

Fly Phoenix fly

It's time for a new empire

Go bury your demons then tear down the ceiling

Phoenix fly

题目描述

给定一个长度为 $n$ 的序列 $a$ 以及一个长度为 $m$ 的序列 $b$ 。

定义一次操作过程如下：

1. 选择集合 $S\subseteq \{1,2,\dots,n\}$ 。

2. 对于 $x\in S$ ，$a_x:=b_{a_x}$ 。

你想知道最少多少次操作才能使 $a$ 形成单调不降的序列，即对于 $1\le i<n$ ，$a_i\le a_{i+1}$ 。

输入格式

第一行一个整数 $n,m$ ，分别代表序列 $a,b$ 的长度。

第二行 $n$ 个整数，代表序列 $a$ 。

第三行 $m$ 个整数，代表序列 $b$ 。

输出格式

输出一行一个整数，代表问题的答案。若无解输出 $-1$ 。

样例

样例输入

5 8
1 6 3 7 1
2 3 5 8 7 1 5 6

样例输出

3

数据范围

对于所有数据，$1\le n,m\le 10^6,1\le a_i,b_i\le m$ 。

子任务 1 ( 20% ) : $1\le n,m\le 1000$ 。

子任务 2 ( 10% ) ：对于 $2\le i\le m$ ，$b_i=i-1$ 。

子任务 3 ( 10% ) ：对于 $2\le i\le m$ , $b_i=1$。

子任务 4 ( 20% ) ：对于任意 $1\le x\le m$ ，若不断令 $x:=b_x$ ，最后一定会使 $x$ 与 $b_x$ 相等。

子任务 5 ( 20% ) ：$1\le n,m\le 3*10^5$ 。

子任务 6 ( 20% ) : 无特殊限制。