题目背景

请在提交时不要引用 hieroglyphs.h。

请勿用 C++14 (GCC 9) 提交。

题目描述

一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究，他们采用了关于序列的如下概念。

对于一个给定的序列 $A$，某个序列 $S$ 被称为是 $A$ 的子序列，当且仅当 $S$ 能够通过移除 $A$ 中的某些（也可能零个）元素而得到。

下表给出了序列 $A = [3, 2, 1, 2]$ 的子序列的一部分例子。

子序列	由 $A$ 得到子序列的方式
[3, 2, 1, 2]	不移除任何元素。
[2, 1, 2]	[3, 2, 1, 2]
[3, 2, 2]	[3, 2, 1, 2]
[3, 2]	[3, 2, 1, 2] 或者 [3, 2, 1, 2]
[3]	[3, 2, 1, 2]
[ ]	[3, 2, 1, 2]

另一方面，$[3, 3]$ 或 $[1, 3]$ 不是 $A$ 的子序列。

考虑有两个象形文字序列 $A$ 和 $B$。某个序列 $S$ 被称为是 $A$ 和 $B$ 的公共子序列，当且仅当 $S$ 同时是 $A$ 和 $B$ 的子序列。此外，我们说某个序列 $U$ 是 $A$ 和 $B$ 的一个最全公共子序列，当且仅当如下两个条件成立：

• $U$ 是 $A$ 和 $B$ 的一个公共子序列。
• $A$ 和 $B$ 的任意公共子序列，都是 $U$ 的一个子序列。

可以证明，任意两个序列 $A$ 和 $B$ 都至多有一个最全公共子序列。

研究人员发现了两个象形文字序列 $A$ 和 $B$。序列 $A$ 包含 $N$ 个象形文字，而序列 $B$ 包含 $M$ 个象形文字。请帮助研究人员为序列 $A$ 和 $B$ 找到一个最全公共子序列，或者判定这样的序列并不存在。

输入格式

N  M
A[0]  A[1]  ...  A[N-1]
B[0]  B[1]  ...  B[M-1]

输出格式

T
R[0]  R[1]  ...  R[T-1]

这里 $R$ 是 ucs 所返回的数组，而 $T$ 为其长度。

6 5
0 0 1 0 1 2
2 0 1 0 2

4
0 1 0 2

3 2
0 0 2
1 1

0

3 3
0 1 0
1 0 1

1
-1

提示

实现细节

你要实现以下函数。

std::vector<int> ucs(std::vector<int> A, std::vector<int> B)

• $A$：长度为 $N$ 的数组，给出第一个序列。
• $B$：长度为 $M$ 的数组，给出第二个序列。
• 如果 $A$ 和 $B$ 有一个最全公共子序列，该函数应当返回一个包含该序列的数组。否则，该函数应当返回 $[-1]$（一个长度为 $1$ 的数组，其唯一元素为 $-1$）。
• 对每个测试用例，该函数恰好被调用一次。

约束条件

• $1 \leq N \leq 100\,000$
• $1 \leq M \leq 100\,000$
• 对所有满足 $0 \leq i < N$ 的 $i$，都有 $0 \leq A[i] \leq 200\,000$
• 对所有满足 $0 \leq j < M$ 的 $j$，都有 $0 \leq B[j] \leq 200\,000$

子任务

子任务	分数	额外的约束条件
1	$3$	$N = M$；$A$ 和 $B$ 均由 $N$ 个不同的整数构成，取自 $0$ 到 $N-1$（包括这两个值）
2	$15$	对任意整数 $k$，$k$ 在 $A$ 和 $B$ 中的出现次数，加起来至多等于 $3$。
3	$10$	对所有满足 $0 \leq i < N$ 的 $i$，都有 $A[i] \leq 1$；对所有满足 $0 \leq j < M$ 的 $j$，都有 $B[j] \leq 1$
4	$16$	$A$ 和 $B$ 存在最全公共子序列。
5	$14$	$N \leq 3000$；$M \leq 3000$
6	$42$	没有额外的约束条件。

例子

例 1

考虑以下函数调用。

ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])

此时，$A$ 和 $B$ 的公共子序列为：$[\ ]$，$[0]$，$[1]$，$[2]$，$[0, 0]$，$[0, 1]$，$[0, 2]$，$[1, 0]$，$[1, 2]$，$[0, 0, 2]$，$[0, 1, 0]$，$[0, 1, 2]$，$[1, 0, 2]$ 和 $[0, 1, 0, 2]$。

由于 $[0, 1, 0, 2]$ 是 $A$ 和 $B$ 的一个公共子序列，而 $A$ 和 $B$ 的所有公共子序列又都是 $[0, 1, 0, 2]$ 的子序列，因此函数应该返回 $[0, 1, 0, 2]$。

例 2

考虑以下函数调用。

ucs([0, 0, 2], [1, 1])

此时，$A$ 和 $B$ 唯一的公共子序列为空序列 $[\ ]$。因此函数应该返回一个空数组 $[\ ]$。

例 3

考虑以下函数调用。

ucs([0, 1, 0], [1, 0, 1])

此时，$A$ 和 $B$ 的公共子序列为 $[\ ]$，$[0]$，$[1]$，$[0, 1]$ 和 $[1, 0]$，可以看出两者并不存在最全公共子序列。因此，函数应该返回 $[-1]$。