Background

Please do not include hieroglyphs.h when submitting.

Do not submit in C++14 (GCC 9).

Problem Description

A research team is studying the similarity between hieroglyph sequences. They represent each hieroglyph as a non-negative integer. For their research, they use the following concepts about sequences.

For a given sequence $A$, a sequence $S$ is called a subsequence of $A$ if and only if $S$ can be obtained by removing some (possibly zero) elements from $A$.

The table below shows some examples of subsequences of the sequence $A = [3, 2, 1, 2]$.

On the other hand, $[3, 3]$ or $[1, 3]$ is not a subsequence of $A$.

Now consider two hieroglyph sequences $A$ and $B$. A sequence $S$ is called a common subsequence of $A$ and $B$ if and only if $S$ is a subsequence of both $A$ and $B$. Furthermore, we say that a sequence $U$ is a universal common subsequence of $A$ and $B$ if and only if the following two conditions hold:

• $U$ is a common subsequence of $A$ and $B$.
• Every common subsequence of $A$ and $B$ is a subsequence of $U$.

It can be proven that any two sequences $A$ and $B$ have at most one universal common subsequence.

The researchers found two hieroglyph sequences $A$ and $B$. Sequence $A$ contains $N$ hieroglyphs, and sequence $B$ contains $M$ hieroglyphs. Please help the researchers find a universal common subsequence of $A$ and $B$, or determine that such a sequence does not exist.

Input Format

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

Output Format

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

Here, $R$ is the array returned by ucs, and $T$ is its length.

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

Hint

Description

Implementation Details

You have to implement the following function.

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

• $A$: an array of length $N$, giving the first sequence.
• $B$: an array of length $M$, giving the second sequence.
• If $A$ and $B$ have a universal common subsequence, the function should return an array containing that sequence. Otherwise, the function should return $[-1]$ (an array of length $1$ whose only element is $-1$).
• For each test case, this function is called exactly once.

Input Format

Constraints

• $1 \leq N \leq 100\,000$
• $1 \leq M \leq 100\,000$
• For all $i$ with $0 \leq i < N$, $0 \leq A[i] \leq 200\,000$
• For all $j$ with $0 \leq j < M$, $0 \leq B[j] \leq 200\,000$

Subtasks

Examples

Example 1

Consider the following function call.

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

In this case, the common subsequences of $A$ and $B$ are: $[\ ]$, $[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]$, and $[0, 1, 0, 2]$.

Since $[0, 1, 0, 2]$ is a common subsequence of $A$ and $B$, and all common subsequences of $A$ and $B$ are subsequences of $[0, 1, 0, 2]$, the function should return $[0, 1, 0, 2]$.

Example 2

Consider the following function call.

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

In this case, the only common subsequence of $A$ and $B$ is the empty sequence $[\ ]$. Therefore, the function should return an empty array $[\ ]$.

Example 3

Consider the following function call.

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

In this case, the common subsequences of $A$ and $B$ are $[\ ]$, $[0]$, $[1]$, $[0, 1]$, and $[1, 0]$. We can see that a universal common subsequence does not exist. Therefore, the function should return $[-1]$.

Output Format

Hint

Translated by ChatGPT 5