問題文

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

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

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

入力

$NM$
$p_1{q}_1{a}_1{b}_1$
...
$p_M{q}_M{a}_M{b}_M$

• 入力は全て整数
• $2\le N\le {10}^5$
• $1\le M\le {10}^5$
• $1\le p_i<q_i\le N$
• $1\le a_i{b}_i\le 3$

出力

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

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

サンプル

3 2
1 2 1 2
2 3 2 1

1 2 3