B. Игра в MEX
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для мультимножества $$$\mathcal{S}$$$ и положительного целого числа $$$k$$$ обозначим через $$$\operatorname{mex}_k(\mathcal{S})$$$ наименьшее неотрицательное целое число, которое встречается в $$$\mathcal{S}$$$ менее $$$k$$$ раз. В частности, $$$\operatorname{mex}_1(\mathcal{S})$$$ — это обычный $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$ мультимножества $$$\mathcal{S}$$$.

Например:

  • $$$\operatorname{mex}_1(\{0, 1, 1, 2\}) = 3$$$;
  • $$$\operatorname{mex}_2(\{0, 0, 1, 1, 1, 3\}) = 2$$$;
  • $$$\operatorname{mex}_2(\{0, 1, 1, 2\}) = 0$$$;
  • $$$\operatorname{mex}_2(\{0, 0, 1, 2\}) = 1$$$.

Даны чётное целое число $$$n$$$, положительное целое число $$$k$$$ и $$$n$$$ карточек. На $$$i$$$-й карточке записано целое число $$$a_i$$$.

Алиса и Боб играют с этими карточками в следующую игру. Игроки ходят по очереди, первой ходит Алиса. На каждом ходу игрок берёт любую одну из оставшихся карточек. Игра заканчивается, когда все $$$n$$$ карточек разобраны, поэтому у каждого игрока оказывается ровно $$$\dfrac{n}{2}$$$ карточек.

Пусть $$$\mathcal{A}$$$ — мультимножество чисел, записанных на карточках Алисы, а $$$\mathcal{B}$$$ — мультимножество чисел, записанных на карточках Боба. Алиса побеждает, если $$$\operatorname{mex}_k(\mathcal{A}) \ne \operatorname{mex}_k(\mathcal{B})$$$, а иначе побеждает Боб.

Определите, победит ли Алиса, если оба игрока играют оптимально.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_m$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n$$$ — чётное, $$$1 \le k \le n$$$) — количество карточек и параметр игры.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — числа, записанные на карточках.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если Алиса побеждает, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
4 1
2 0 0 1
4 1
0 1 0 1
6 2
1 2 0 1 0 0
6 2
0 0 1 1 2 2
8 2
0 1 1 0 0 2 0 1
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом примере Алиса может взять карточку с числом $$$1$$$ на своём первом ходу и карточку с числом $$$0$$$ на своём втором ходу. Тогда $$$\mathcal{A} = \{0, 1\}$$$ и $$$\mathcal{B} = \{0, 2\}$$$, поэтому $$$\operatorname{mex}_1(\mathcal{A}) = 2$$$ и $$$\operatorname{mex}_1(\mathcal{B}) = 1$$$. Можно доказать, что Алиса побеждает независимо от ходов Боба, поэтому ответ — «YES».

Во втором примере игроки могут брать карточки в следующем порядке: Алиса берёт $$$1$$$, Боб берёт $$$1$$$, Алиса берёт $$$0$$$, Боб берёт $$$0$$$. Тогда $$$\mathcal{A} = \mathcal{B} = \{0, 1\}$$$ и $$$\operatorname{mex}_1(\mathcal{A}) = \operatorname{mex}_1(\mathcal{B}) = 2$$$. Можно доказать, что Боб побеждает, если оба игрока играют оптимально, поэтому ответ — «NO».