Даны массив \(a\) из \(n\) целых чисел, массив \(b\) из \(m\) целых чисел и чётное число \(k\).
Ваша задача определить, возможно ли выбрать ровно \(\frac{k}{2}\) элементов из обоих массивов так, чтобы среди выбранных элементов встречалось каждое целое число от \(1\) до \(k\).
Например:
- Если \(a=[2, 3, 8, 5, 6, 5]\), \(b=[1, 3, 4, 10, 5]\), \(k=6\), то можно выбрать элементы со значениями \(2, 3, 6\) из массива \(a\) и элементы со значениями \(1, 4, 5\) из массива \(b\). В таком случае, среди выбранных элементов будут встречаться все числа от \(1\) до \(k=6\).
- Если \(a=[2, 3, 4, 5, 6, 5]\), \(b=[1, 3, 8, 10, 3]\), \(k=6\), то выбрать элементы таким образом невозможно.
Обратите внимание, что от вас не требуется найти способ выбора элементов — ваша программа должна лишь проверять, возможно ли выбрать элементы требуемым образом.
Выходные данные
Выведите \(t\) строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если существует способ выбрать по \(\frac{k}{2}\) чисел из каждого массива так, чтобы среди выбранных элементов встречалось каждое целочисленное значение от \(1\) до \(k\). Иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных примера можно выбрать элементы, равные \(2\), \(3\) и \(6\) из массива \(a\) и элементы равные \(1\), \(4\) и \(5\) из массива \(b\). Таким образом, среди выбранных элементов встречается каждое число от \(1\) до \(k=6\).
Во втором наборе входных данных примера можно показать, что выбрать ровно три элемента из каждого массива требуемым образом невозможно.
В третьем наборе входных данных примера можно выбрать элементы, равные \(1\) и \(3\) из массива \(a\) и элементы равные \(2\) и \(4\) из массива \(b\). Таким образом, среди выбранных элементов встречается каждое число от \(1\) до \(k=4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3
|
YES
NO
YES
YES
NO
NO
|