Busy Beaver пытается поступить в MIT. Вместо сдачи SAT он считает, что может добиться большего — в три раза большего, и поэтому берется за решение 3-SAT! Он нашел поистине удивительное решение, но, к сожалению, поля его заявления оказались слишком узкими, чтобы его вместить. Поэтому он придумал свою собственную версию задачи, но ему нужна ваша помощь в её решении:

Пусть $n, m$ — положительные целые числа. Имеется $n$ переменных $x_1, \dots, x_n$, принимающих значения в $\{0, 1\}$. Клауза — это произведение трех переменных $x_a \cdot x_b \cdot x_c$ с индексами $1 \le a \le b \le c \le n$. Вам дано выражение, представляющее собой сумму $m$ таких клауз. Например, одно из таких выражений для четырех переменных с тремя клаузами может выглядеть так: $$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4.$$

Определите, можно ли выбрать значения $x_1, \dots, x_n$ так, чтобы итоговое выражение было нечетным.

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

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

В первой строке каждого набора содержится два целых числа $n, m$ ($1 \le n, m \le 10^5$).

Следующие $m$ строк каждого набора описывают каждую из клауз в сумме. $i$-я из них состоит из трех целых чисел $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$), разделенных пробелами, что означает, что $i$-я клауза суммы равна $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$.

Гарантируется, что сумма $n$ и сумма $m$ по всем наборам входных данных не превышают $10^5$.

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

Для каждого набора входных данных выведите одну строку, содержащую строку YES, если существует такой набор значений $x_i$, при котором выражение становится нечетным, и NO в противном случае. Вы можете выводить каждую букву в любом регистре. Например, yes, Yes, YeS будут распознаны как положительный ответ.

Затем, если вы ответили YES, выведите вторую строку, состоящую из $n$ целых чисел $x_1, \dots, x_n$ ($x_i = 0$ или $1$), которые делают значение выражения нечетным. Если существует несколько возможных решений, выведите любое из них.

Подзадачи

Вы получите 50% баллов за каждую подзадачу, если ответы YES/NO верны, но предоставленные значения $x_i$ — нет. Для каждого набора входных данных вы должны вывести ровно $n$ значений $x_i$ для получения частичных баллов.

• (50 баллов): В каждой клаузе ни одна переменная не встречается более одного раза, т.е. $a_i < b_i < c_i$.
• (50 баллов): Дополнительных ограничений нет.

Примеры

Пример 1

2
4 3
1 2 3
1 3 4
2 3 4
3 2
1 2 3
1 2 3

Пример 2

YES
1 1 1 1
NO

Примечание

Первый набор входных данных идентичен примеру в условии задачи. В этом выражении установка всех переменных в 1 делает выражение равным $1 + 1 + 1 = 3$, что является нечетным числом.

Во втором наборе входных данных заданное выражение равно $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$. Можно показать, что не существует такой установки $x_1, x_2, x_3$, которая делает это выражение нечетным.