← 返回题目列表

Codeforces · 1382/A

A. 公共子序列

中文机器翻译题面 查看原题

给定两个整数数组 $$$a_1,\ldots,a_n$$$ 和 $$$b_1,\ldots,b_m$$$。

你的任务是找到一个非空数组 $$$c_1,\ldots,c_k$$$,它是 $$$a_1,\ldots,a_n$$$ 的子序列,也是 $$$b_1,\ldots,b_m$$$ 的子序列。如果有多个答案,请找到尽可能最小的长度之一。如果仍然存在最小可能长度的倍数,则找到其中任何一个。如果没有这样的数组,您应该报告它。

如果 $$$a$$$ 可以通过删除几个(可能是零)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。例如,$$$[3,1]$$$ 是 $$$[3,2,1]$$$ 和 $$$[4,3,1]$$$ 的子序列,但不是 $$$[1,3,3,7]$$$ 和 $$$[3,10,4]$$$ 的子序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。接下来的 $$$3t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,m\le 1000$$$) — 两个数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 1000$$$) — 第一个数组的元素。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1,\ldots,b_m$$$ ($$$1\le b_i\le 1000$$$) — 第二个数组的元素。

保证所有测试用例的 $$$n$$$ 总和与 $$$m$$$ 总和不超过 $$$1000$$$ ($$$\sum\limits_{i=1}^t n_i, \sum\limits_{i=1}^t m_i\le 1000$$$)。

输出

对于每个测试用例,如果存在解决方案,则输出“YES”,否则输出“NO”。

如果答案为“YES”,则在下一行输出一个整数 $$$k$$$ ($$$1\le k\le 1000$$$) — 数组的长度,后跟 $$$k$$$ 整数 $$$c_1,\ldots,c_k$$$ ($$$1\le c_i\le 1000$$$) — 的元素数组。

如果存在多个具有最小可能 $$$k$$$ 的解,则输出任意一个。

示例

输入 #1

5
4 5
10 8 6 4
1 2 3 4 5
1 1
3
3
1 1
3
2
5 3
1000 2 2 2 3
3 1 5
5 5
1 2 3 4 5
1 2 3 4 5

输出 #1

YES
1 4
YES
1 3
NO
YES
1 3
YES
1 2

注意

在第一个测试用例中,$$$[4]$$$ 是 $$$[10, 8, 6, 4]$$$ 和 $$$[1, 2, 3, 4, 5]$$$ 的子序列。该数组的长度为$$$1$$$,它是$$$a$$$ 和$$$b$$$ 的子序列的最小可能长度。

在第三个测试用例中,$$$[3]$$$ 和 $$$[2]$$$ 都不存在非空子序列,因此答案为“NO”。