There are $n$ boolean variables $x_1, x_2, \dots, x_n$.

There are $m$ constraints, each of the form: $x_a = b \vee x_c = d$.

Construct a valid assignment of values such that all constraints are satisfied.

Input

The first line of input contains two integers $n$ and $m$.

The next $m$ lines each contain four integers $a, b, c, d$.

Output

If there is no solution, output a single line containing No.

Otherwise, first output a line containing Yes. Then, output a line containing $n$ integers representing your construction.

Subtasks

For all data, $1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5$.

Examples

Input 1

3 3
1 0 2 0
2 1 3 1
3 0 1 0

Output 1

Yes
0 0 1

Input 2

4 6
1 0 2 0
1 0 3 0
2 0 3 0
1 1 2 1
1 1 3 1
2 1 3 1

Output 2

No