Problem Statement

Determine whether there exists a sequence $(x_1,\dots,x_N)$ of length $N$, each of whose elements is one of $1,2,3$, that satisfies all of the following $M$ conditions $1,\dots,M$.

Furthermore, if one exists, show one example of such a sequence.

• Condition $i$: at least one of $x_{p_i} = a_i$ and $x_{q_i} = b_i$ holds.

Input

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

• All inputs are integers.
• $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$

Output

If there exists $(x_1,\dots,x_N)$ satisfying all the conditions, output one of them, separated by spaces.

If none exists, output -1.

Sample

3 2
1 2 1 2
2 3 2 1

1 2 3