Busy Beaver próbuje dostać się na MIT. Zamiast przystępować do SAT, uważa, że może poradzić sobie lepiej — trzy razy lepiej, ponieważ postanowił rozwiązać 3-SAT! Znalazł doprawdy cudowne rozwiązanie, ale niestety marginesy jego podania były zbyt wąskie, by je pomieścić. Wymyślił więc własną wersję problemu, ale potrzebuje Twojej pomocy w jej rozwiązaniu:

Niech $n, m$ będą dodatnimi liczbami całkowitymi. Istnieje $n$ zmiennych $x_1, \dots, x_n$ przyjmujących wartości w $\{0, 1\}$. Klauzula to iloczyn trzech zmiennych $x_a \cdot x_b \cdot x_c$ o indeksach $1 \le a \le b \le c \le n$. Otrzymujesz wyrażenie będące sumą $m$ takich klauzul. Na przykład, jedno z takich wyrażeń dla czterech zmiennych z trzema klauzulami może wyglądać następująco:

$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4$$

Określ, czy możliwe jest dobranie wartości $x_1, \dots, x_n$ tak, aby wynikowe wyrażenie było nieparzyste.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^5$).

Dalej następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $n, m$ ($1 \le n, m \le 10^5$).

Kolejne $m$ linii każdego przypadku testowego opisuje każdą z klauzul w sumie. $i$-ta z nich składa się z trzech oddzielonych spacjami liczb całkowitych $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$), oznaczających, że $i$-ta klauzula sumy to $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$.

Gwarantuje się, że suma $n$ oraz suma $m$ we wszystkich przypadkach testowych nie przekraczają $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w jednej linii ciąg znaków YES, jeśli istnieje takie ustawienie $x_i$, aby wyrażenie było nieparzyste, oraz NO w przeciwnym razie. Możesz wypisać każdą literę w dowolnej wielkości. Na przykład, yes, Yes, YeS będą rozpoznane jako odpowiedź twierdząca.

Następnie, jeśli odpowiedziałeś YES, wypisz w drugiej linii $n$ oddzielonych spacjami liczb całkowitych $x_1, \dots, x_n$ ($x_i = 0$ lub $1$), które sprawiają, że wyrażenie przyjmuje wartość nieparzystą. Jeśli istnieje wiele możliwych rozwiązań, wypisz dowolne z nich.

Podzadania

Otrzymasz 50% punktów za każde podzadanie, jeśli odpowiedzi YES/NO są poprawne, ale podane wartości $x_i$ nie są. Dla każdego przypadku testowego musisz wypisać dokładnie $n$ wartości $x_i$, aby otrzymać punkty częściowe.

• (50 punktów): W każdej klauzuli żadna zmienna nie pojawia się więcej niż raz, tzn. $a_i < b_i < c_i$.
• (50 punktów): Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

YES
1 1 1 1
NO

Uwagi

Pierwszy przypadek testowy jest identyczny z przykładem w treści zadania. W tym wyrażeniu ustawienie wszystkich zmiennych na 1 sprawia, że wyrażenie jest równe $1 + 1 + 1 = 3$, co jest liczbą nieparzystą.

W drugim przypadku testowym dane wyrażenie to $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$. Można wykazać, że żadne ustawienie $x_1, x_2, x_3$ nie czyni tego wyrażenia nieparzystym.