#K49377. Merging Sorted Arrays Possibility

    ID: 28629 Type: Default 1000ms 256MiB

Merging Sorted Arrays Possibility

Merging Sorted Arrays Possibility

You are given two arrays B and C of lengths P and Q respectively. You are allowed to reorder each of the two arrays arbitrarily (i.e. permute the elements). Your task is to determine if it is possible to reorder B and C such that when they are merged (by simply concatenating the two arrays after reordering) the resulting array is non-decreasing.

A sufficient strategy is to sort both arrays in non-decreasing order and then check for each index i (from 0 to \( \min(P, Q) - 1 \)) whether \(B[i] \le C[i]\). If this condition holds for all such indices then the answer is YES, otherwise it is NO.

Note: The merged array does not require the elements of the two segments to be interleaved; they are simply concatenated after reordering. However, the check described above is a necessary and sufficient condition for the existence of a valid reordering under these problem constraints.

inputFormat

The input is read from stdin and has the following format:

T
P Q
B1 B2 ... BP
C1 C2 ... CQ
... (repeated for each test case)

Here, T is the number of test cases. For each test case, the first line contains two integers P and Q representing the lengths of arrays B and C. The next line contains P integers (elements of B) and the following line contains Q integers (elements of C).

outputFormat

For each test case, output a single line containing either YES or NO on stdout indicating whether it is possible to reorder the arrays to obtain a non-decreasing merged array.

## sample
2
3 4
3 1 2
4 6 5 7
2 2
5 8
1 3
YES

NO

</p>