[Solution] Equal LCM Subsets solution codeforces

Equal LCM Subsets solution codeforces – You are given two sets of positive integers 𝐴A and 𝐵B. You have to find two non-empty subsets 𝑆𝐴𝐴SA⊆A𝑆𝐵𝐵SB⊆B so that the least common multiple (LCM) of the elements of 𝑆𝐴SA is equal to the least common multiple (LCM) of the elements of 𝑆𝐵SB.

Equal LCM Subsets solution codeforces

Input

The input consists of multiple test cases. The first line of the input contains one integer 𝑡t (1𝑡2001≤t≤200), the number of test cases.

For each test case, there is one line containing two integers 𝑛,𝑚n,m (1𝑛,𝑚10001≤n,m≤1000), the sizes of the sets 𝐴A and 𝐵B, respectively.

The next line contains 𝑛n distinct integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖410361≤ai≤4⋅1036), the elements of 𝐴A.

The next line contains 𝑚m distinct integers 𝑏1,𝑏2,,𝑏𝑚b1,b2,…,bm (1𝑏𝑖410361≤bi≤4⋅1036), the elements of 𝐵B.

The sum of 𝑛n for all test cases and the sum of 𝑚m for all test cases is at most 10001000.

Equal LCM Subsets solution codeforces

For each test case, if there do not exist two subsets with equal least common multiple, output one line with NO.

Otherwise, output one line with YES, followed by a line with two integers |𝑆𝐴|,|𝑆𝐵||SA|,|SB| (1|𝑆𝐴|𝑛1≤|SA|≤n1|𝑆𝐵|𝑚1≤|SB|≤m), the sizes of the subsets 𝑆𝐴SA and 𝑆𝐵SB

The next line should contain |𝑆𝐴||SA| integers 𝑥1,𝑥2,,𝑥|𝑆𝐴|x1,x2,…,x|SA|, the elements of 𝑆𝐴SA, followed by a line with |𝑆𝐵||SB| integers 𝑦1,𝑦2,,𝑦|𝑆𝐵|y1,y2,…,y|SB|, the elements of 𝑆𝐵SB. If there are multiple possible pairs of subsets, you can print any.

Example
input

Copy
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

Equal LCM Subsets solution codeforces

output

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

 

For Solution

Click Here

Leave a Comment