Busy Beaver 正在嘗試進入 MIT。他沒有去參加 SAT，而是認為自己可以做得更好——好上三倍，因為他著手解決 3-SAT！他找到了一個非常美妙的解法，但不幸的是，他申請文件的邊緣太窄，寫不下這個解法。因此，他想出了自己版本的題目，但他需要你的幫助來解決它：

令 $n, m$ 為正整數。有 $n$ 個變數 $x_1, \dots, x_n$，其取值範圍為 $\{0, 1\}$。一個子句（clause）是三個變數 $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$。

輸出格式

對於每個測試案例，若存在一組 $x_i$ 的設定使得表達式為奇數，請輸出一行字串 YES，否則輸出 NO。你可以使用任意大小寫字母。例如，yes、Yes、YeS 都會被視為肯定回答。

接著，如果你回答了 YES，請輸出第二行，包含以空格分隔的整數 $x_1, \dots, x_n$ ($x_i = 0$ 或 $1$)，使得表達式計算結果為奇數。若有多種可能的解，輸出其中任意一個即可。

子任務

如果你正確回答了 YES/NO，但提供的 $x_i$ 值不正確，你將獲得該子任務 50% 的分數。對於每個測試案例，你必須輸出恰好 $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

輸出 1

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$ 的設定能使該表達式為奇數。