Busy Beaver está intentando entrar al MIT. En lugar de tomar el SAT, piensa que puede hacerlo mejor — tres veces mejor, mientras se propone resolver 3-SAT. Ha encontrado una solución verdaderamente maravillosa, pero desafortunadamente, los márgenes de su solicitud eran demasiado estrechos para contenerla. Así que, se le ocurrió su propia versión del problema, pero necesita tu ayuda para resolverla:

Sean $n, m$ enteros positivos. Hay $n$ variables $x_1, \dots, x_n$ que toman valores en $\{0, 1\}$. Una cláusula es un producto de tres variables $x_a \cdot x_b \cdot x_c$ con índices $1 \leq a \leq b \leq c \leq n$. Se te da una expresión que es una suma de $m$ cláusulas de este tipo. Por ejemplo, una de estas expresiones con cuatro variables y tres cláusulas podría ser:

$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4$$

Determina si es posible elegir los valores $x_1, \dots, x_n$ de tal manera que la expresión resultante sea impar.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \leq t \leq 10^5$).

La descripción de los casos de prueba sigue a continuación.

La primera línea de cada caso de prueba contiene dos enteros $n, m$ ($1 \leq n, m \leq 10^5$).

Las siguientes $m$ líneas de cada caso de prueba describen cada una de las cláusulas en la suma. La $i$-ésima de ellas consiste en tres enteros separados por espacios $a_i, b_i, c_i$ ($1 \leq a_i \leq b_i \leq c_i \leq n$), lo que denota que la $i$-ésima cláusula de la suma es $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$.

Se garantiza que la suma de $n$ y la suma de $m$ sobre todos los casos de prueba no exceden $10^5$.

Salida

Para cada caso de prueba, imprime una línea que contenga la cadena YES si existe una configuración de las $x_i$ para hacer que la expresión sea impar, y NO en caso contrario. Puedes imprimir cada letra en cualquier combinación de mayúsculas y minúsculas. Por ejemplo, yes, Yes, YeS serán reconocidas como una respuesta positiva.

Luego, si respondiste con YES, imprime una segunda línea que consista en enteros separados por espacios $x_1, \dots, x_n$ ($x_i = 0$ o $1$) que hagan que la expresión se evalúe como un número impar. Si hay múltiples soluciones posibles, imprime cualquiera de ellas.

Subtareas

Recibirás el 50% de los puntos por cada subtarea si las respuestas YES/NO son correctas, pero los valores proporcionados de $x_i$ no lo son. Para cada caso de prueba, debes imprimir exactamente $n$ valores de $x_i$ para obtener crédito parcial.

• (50 puntos): Dentro de cada cláusula, ninguna variable aparece más de una vez, es decir, $a_i < b_i < c_i$.
• (50 puntos): Sin restricciones adicionales.

Ejemplos

Entrada 1

2
4 3
1 2 3
1 3 4
2 3 4
3 2
1 2 3
1 2 3

Salida 1

YES
1 1 1 1
NO

Nota

El primer caso de prueba es idéntico al ejemplo en el enunciado del problema. En esta expresión, establecer todas las variables en 1 hace que la expresión sea igual a $1 + 1 + 1 = 3$, lo cual es impar.

En el segundo caso de prueba, la expresión dada es $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$. Se puede demostrar que ninguna configuración de $x_1, x_2, x_3$ hace que esta expresión sea impar.