← 返回题目列表

Codeforces · 1656/H

H. 相等的 LCM 子集

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

给你两组正整数 $$$A$$$ 和 $$$B$$$。您必须找到两个非空子集 $$$S_A \subseteq A$$$、$$$S_B \subseteq B$$$,以便 $$$S_A$$$ 元素的最小公倍数 (LCM) 等于 $$$S_B$$$ 元素的最小公倍数 (LCM)。

输入

输入由多个测试用例组成。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200$$$),即测试用例的数量。

对于每个测试用例,有一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$),分别是集合 $$$A$$$ 和 $$$B$$$ 的大小。

下一行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 4 \cdot 10^{36}$$$),$$$A$$$ 的元素。

下一行包含 $$$m$$$ 不同的整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 4 \cdot 10^{36}$$$),$$$B$$$ 的元素。

所有测试用例的 $$$n$$$ 总和以及所有测试用例的 $$$m$$$ 总和最多为 $$$1000$$$。

输出

对于每个测试用例,如果不存在两个最小公倍数相等的子集,则输出一行NO。

否则,输出一行 YES,后跟一行两个整数 $$$|S_A|, |S_B|$$$ ($$$1 \leq |S_A| \leq n$$$, $$$1 \leq |S_B| \leq m$$$),子集 $$$S_A$$$ 和 $$$S_B$$$ 的大小

下一行应包含 $$$|S_A|$$$ 整数 $$$x_1, x_2, \ldots, x_{|S_A|}$$$,$$$S_A$$$ 的元素,后跟一行 $$$|S_B|$$$ 整数 $$$y_1, y_2, \ldots, y_{|S_B|}$$$,$$$S_B$$$ 的元素。如果存在多个可能的子集对,则可以打印任何一个。

示例

输入 #1

4
3 4
5 6 7
2 8 9 10
4 4
5 6 7 8
2 3 4 9
1 3
1
1 2 3
5 6
3 4 9 7 8
2 15 11 14 20 12

输出 #1

NO
YES
1 2
6
2 3
YES
1 1
1
1
YES
3 2
3 7 4
12 14