牛牛的子序列
题号:NC300761
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}牛牛给你一个整数序列 a_1, a_2, \dots, a_n,你可以执行以下操作任意次(可以是零次):
\hspace{23pt}\bullet\,选择当前序列的一个子序列,将该子序列中的每个元素各复制一份,并分别紧跟其在当前序列中的位置之后插入(即每个被选中的元素右侧立即插入一个与其相等的新元素)。例如 \{1,2,3,4\} 可以选择子序列 \{2,4\},而后序列 a 变为 \{1,2,{\color{orange}{2}},3,4,{\color{orange}{4}}\}
\hspace{15pt}给出目标序列 b_1, b_2, \dots, b_m,求解从 a 变成 b 至少需要几次操作。

【名词解释】
\hspace{15pt}子序列:从原序列中删除任意个(可以为零、可以为全部)元素得到的新序列。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 100\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}第一行输入两个整数 n,m \left(1\le n,m\le 2\times 10^5\right),表示数组 ab 中的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(1\le a_i\le 10^9\right),表示数组 a 中的元素。
\hspace{15pt}第三行输入 m 个整数 b_1,b_2,\dots,b_m \left(1\le b_i\le 10^9\right),表示数组 b 中的元素。
\hspace{15pt}除此之外,保证单个测试文件的 n 之和、m 之和均不超过 2\times 10^5

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行。如果无论如何都无法得到目标数组 b,直接输出 -1;否则,输出一个整数,表示最少需要的操作次数。
示例1

输入

复制
4
4 12
1 2 3 1
1 1 2 2 2 2 3 3 3 3 1 1
1 4
1
1 2 3 4
3 9
1 2 3
1 1 1 2 2 2 3 3 3
5 5
1 1 2 1 1
1 1 2 1 1

输出

复制
2
-1
2
0