Busy Beaver は MIT への入学を目指しています。SAT を受ける代わりに、彼はもっと良い方法、つまり 3 倍良い方法があると考え、3-SAT を解くことにしました！彼は本当に素晴らしい解法を見つけましたが、残念なことに、彼の応募書類の余白が狭すぎてそれを書き込むことができませんでした。そこで彼はこの問題の独自のバージョンを考え出しましたが、それを解くためにあなたの助けが必要です。

$n, m$ を正の整数とします。$\{0, 1\}$ の値をとる $n$ 個の変数 $x_1, \dots, x_n$ があります。節（clause）とは、添字 $1 \le a \le b \le c \le n$ を持つ 3 つの変数 $x_a \cdot x_b \cdot x_c$ の積です。あなたは、$m$ 個のそのような節の和である式を与えられます。例えば、4 つの変数と 3 つの節を持つそのような式は以下のようになります。

$$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$) が含まれます。 続いて各テストケースの説明が続きます。 各テストケースの最初の行には、2 つの整数 $n, m$ ($1 \le n, m \le 10^5$) が含まれます。 各テストケースの続く $m$ 行は、和に含まれる各節を記述します。そのうちの $i$ 番目の行は、3 つのスペース区切りの整数 $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 を 1 行に出力してください。各文字は大文字・小文字を問いません。例えば、yes, Yes, YeS はすべて肯定的な回答として認識されます。

次に、YES と回答した場合は、式を奇数に評価させるようなスペース区切りの整数 $x_1, \dots, x_n$ ($x_i = 0$ または $1$) からなる 2 行目を出力してください。複数の可能な解がある場合は、そのうちのいずれかを出力してください。

小課題

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$ となり、これは奇数です。

2 番目のテストケースでは、与えられた式は $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$ です。$x_1, x_2, x_3$ のどのような設定でもこの式を奇数にすることはできないことが示せます。