Codeforces Round 923 (Div. 3) |
---|
Закончено |
Даны массив $$$a$$$ из $$$n$$$ целых чисел, массив $$$b$$$ из $$$m$$$ целых чисел и чётное число $$$k$$$.
Ваша задача определить, возможно ли выбрать ровно $$$\frac{k}{2}$$$ элементов из обоих массивов так, чтобы среди выбранных элементов встречалось каждое целое число от $$$1$$$ до $$$k$$$.
Например:
Обратите внимание, что от вас не требуется найти способ выбора элементов — ваша программа должна лишь проверять, возможно ли выбрать элементы требуемым образом.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 2\cdot10^5$$$, $$$2 \le k \le 2 \cdot \min(n, m)$$$, $$$k$$$ — чётное число) — длину массива $$$a$$$, длину массива $$$b$$$ и количество элементов, которое нужно выбрать, соответственно.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.
Третья строка каждого набора содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_j \le 10^6$$$) — элементы массива $$$b$$$.
Гарантируется, что сумма значений $$$n$$$ и $$$m$$$ по всем наборам входных данных теста не превосходит $$$4 \cdot 10^5$$$.
Выведите $$$t$$$ строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если существует способ выбрать по $$$\frac{k}{2}$$$ чисел из каждого массива так, чтобы среди выбранных элементов встречалось каждое целочисленное значение от $$$1$$$ до $$$k$$$. Иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
66 5 62 3 8 5 6 51 3 4 10 56 5 62 3 4 5 6 51 3 8 10 33 3 41 3 52 4 62 5 41 47 3 4 4 21 4 226 4 4 21 5 232 2 1 4 3
YES NO YES YES NO NO
В первом наборе входных данных примера можно выбрать элементы, равные $$$2$$$, $$$3$$$ и $$$6$$$ из массива $$$a$$$ и элементы равные $$$1$$$, $$$4$$$ и $$$5$$$ из массива $$$b$$$. Таким образом, среди выбранных элементов встречается каждое число от $$$1$$$ до $$$k=6$$$.
Во втором наборе входных данных примера можно показать, что выбрать ровно три элемента из каждого массива требуемым образом невозможно.
В третьем наборе входных данных примера можно выбрать элементы, равные $$$1$$$ и $$$3$$$ из массива $$$a$$$ и элементы равные $$$2$$$ и $$$4$$$ из массива $$$b$$$. Таким образом, среди выбранных элементов встречается каждое число от $$$1$$$ до $$$k=4$$$.
Название |
---|