Mécontentes de la direction de Farmer John, les vaches ont quitté la ferme et fondé le premier Continental Cowngress. Selon le principe « chaque vache obtient quelque chose qu'elle veut », elles ont choisi le système suivant :
Les $M$ vaches présentes ($1 \leq M \leq 4{,}000$) votent sur $N$ projets de loi ($1 \leq N \leq 1{,}000$). Chacune vote oui ou non (entrée '$Y$' ou '$N$') sur exactement deux projets distincts $B_i$ et $C_i$ ($1 \leq B_i, C_i \leq N$). Les votes sont $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) et $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
Les décisions doivent satisfaire au moins un vote de chaque vache. Si Bessie vote oui au projet 1 et non au projet 2, toute solution valide doit adopter le projet 1 ou rejeter le projet 2 (ou les deux).
À partir des votes, déterminez les résultats conformes aux règles. Sans solution, affichez "IMPOSSIBLE". Sinon, pour chaque projet, affichez :
- $Y$ s'il est adopté dans toute solution.
- $N$ s'il est rejeté dans toute solution.
?s'il existe des solutions où il est adopté et d'autres où il ne l'est pas.
Considérez les votes suivants (deux par vache) :
Projets de loi
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Vache $1$ | OUI | NON | |
| Vache $2$ | NON | NON | |
| Vache $3$ | OUI | OUI | |
| Vache $4$ | OUI | OUI |
Deux solutions satisfont toutes les vaches :
- Le projet 1 est adopté (satisfait les vaches 1, 3 et 4).
- Le projet 2 est rejeté (satisfait la vache 2).
- Le projet 3 peut être adopté ou rejeté (d'où les deux solutions).
Ce sont en fait les seules solutions ; la réponse est donc la chaîne de trois caractères suivante :
YN?
Entrée
Lisez sur l'entrée standard.
- Ligne $1$ : deux entiers séparés par un espace, $N$ et $M$.
- Lignes $2 \ldots M+1$ : la ligne $i+1$ décrit les votes de la vache $i$ avec quatre champs séparés par des espaces : entier, vote, autre entier, autre vote, soit $B_i$, $VB_i$, $C_i$, $VC_i$.
Sortie
Écrivez sur la sortie standard.
- Ligne $1$ : une chaîne de $N$ caractères, dont le $i$-ème est "$Y$" si le projet $i$ doit être adopté, "$N$" s'il doit être rejeté, ou "?" si les votes ne permettent pas de déterminer son résultat.
Sans solution satisfaisant toutes les vaches, affichez une seule ligne "IMPOSSIBLE".
Exemples
Entrée 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Sortie 1
YN?
Auteur du problème : Louis Wasserman, 2010