题目描述

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

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

下表给出了序列 $A = [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$ 找到一个最全公共子序列，或者判定这样的序列并不存在。

实现细节

你要实现以下函数。

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

考虑以下函数调用。

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]$。

评测程序示例

输入格式：

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$ 为其长度。

时间限制：$\texttt{1s}$

空间限制：$\texttt{2048MB}$