問題文

全ての要素が $1,2,3$ のいずれかである長さ $N$ の数列 $(x_1,\dots,x_N)$ であって、 次の $M$ 個の条件 $1,\dots,M$ を全て満たすものが存在するか判定してください。

さらに存在する場合はその一例を示してください。

• 条件 $i$ ： $x_{p_i} = a_i$ と $x_{q_i} = b_i$ の少なくとも一方が成り立つ。

入力

$N\ M$
$p_1\ q_1\ a_1\ b_1$
...
$p_M\ q_M\ a_M\ b_M$

• 入力は全て整数
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq p_i < q_i \leq N$
• $1 \leq a_i\, b_i \leq 3$

出力

条件を全て満たす $(x_1,\dots,x_N)$ が存在するならば、そのうちの一つを空白区切りで出力してください。

存在しないならば-1を出力してください。

サンプル

3 2
1 2 1 2
2 3 2 1

1 2 3