Busy Beaver essaie d'entrer au MIT. Au lieu de passer le SAT, il pense pouvoir faire mieux — trois fois mieux, alors qu'il s'apprête à résoudre le 3-SAT ! Il a trouvé une solution vraiment merveilleuse, mais malheureusement, les marges de sa candidature étaient trop étroites pour la contenir. Il a donc imaginé sa propre version du problème, mais il a besoin de votre aide pour le résoudre :
Soient $n, m$ des entiers positifs. Il y a $n$ variables $x_1, \dots, x_n$ prenant des valeurs dans $\{0, 1\}$. Une clause est un produit de trois variables $x_a \cdot x_b \cdot x_c$ avec des indices $1 \le a \le b \le c \le n$. On vous donne une expression qui est une somme de $m$ clauses de ce type. Par exemple, une telle expression à quatre variables avec trois clauses pourrait être $$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4.$$ Déterminez s'il est possible de choisir les valeurs $x_1, \dots, x_n$ de telle sorte que l'expression résultante soit impaire.
Entrée
Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 10^5$). La description des cas de test suit. La première ligne de chaque cas de test contient deux entiers $n, m$ ($1 \le n, m \le 10^5$). Les $m$ lignes suivantes de chaque cas de test décrivent chacune des clauses de la somme. La $i$-ième d'entre elles consiste en trois entiers séparés par des espaces $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$), indiquant que la $i$-ième clause de la somme est $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$. Il est garanti que la somme de $n$ et la somme de $m$ sur tous les cas de test n'excèdent pas $10^5$.
Sortie
Pour chaque cas de test, affichez une ligne contenant la chaîne YES s'il existe une configuration des $x_i$ rendant l'expression impaire, et NO sinon. Vous pouvez imprimer chaque lettre en majuscules ou minuscules. Par exemple, yes, Yes, YeS seront tous reconnus comme une réponse positive.
Ensuite, si vous avez répondu YES, imprimez une deuxième ligne composée d'entiers séparés par des espaces $x_1, \dots, x_n$ ($x_i = 0$ ou $1$) qui font que l'expression s'évalue en un nombre impair. S'il existe plusieurs solutions possibles, imprimez-en n'importe laquelle.
Sous-tâches
Vous recevrez 50 % des points pour chaque sous-tâche si les réponses YES/NO sont correctes, mais que les valeurs fournies pour $x_i$ ne le sont pas. Pour chaque cas de test, vous devez afficher exactement $n$ valeurs de $x_i$ pour obtenir des points partiels.
- (50 points) : Dans chaque clause, aucune variable n'apparaît plus d'une fois, c'est-à-dire $a_i < b_i < c_i$.
- (50 points) : Aucune contrainte supplémentaire.
Exemples
Entrée 1
2 4 3 1 2 3 1 3 4 2 3 4 3 2 1 2 3 1 2 3
Sortie 1
YES 1 1 1 1 NO
Remarque
Le premier cas de test est identique à l'exemple dans l'énoncé du problème. Dans cette expression, définir toutes les variables à 1 rend l'expression égale à $1 + 1 + 1 = 3$, ce qui est impair.
Dans le deuxième cas de test, l'expression donnée est $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$. On peut montrer qu'aucune configuration de $x_1, x_2, x_3$ ne rend cette expression impaire.