Descontentas con el liderazgo de Farmer John, las vacas se separaron de la granja y fundaron el primer Continental Cowngress. Bajo el principio de que «cada vaca obtiene algo que quiere», decidieron este sistema:
Las $M$ vacas presentes ($1 \leq M \leq 4{,}000$) votan $N$ proyectos de ley ($1 \leq N \leq 1{,}000$). Cada una vota sí o no (entrada '$Y$' o '$N$') exactamente en dos proyectos distintos $B_i$ y $C_i$ ($1 \leq B_i, C_i \leq N$). Los votos son $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) y $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
Las decisiones deben satisfacer al menos un voto de cada vaca. Si Bessie vota sí al proyecto 1 y no al 2, toda solución válida debe aprobar el 1 o rechazar el 2 (o ambas cosas).
A partir de todos los votos, determina los resultados conformes a las reglas. Si no hay solución, imprime "IMPOSSIBLE". Si hay al menos una, para cada proyecto muestra:
- $Y$ si se aprueba en toda solución.
- $N$ si se rechaza en toda solución.
?si hay soluciones que lo aprueban y otras que no.
Considera estos votos (dos por vaca):
Proyectos de ley
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Vaca $1$ | SÍ | NO | |
| Vaca $2$ | NO | NO | |
| Vaca $3$ | SÍ | SÍ | |
| Vaca $4$ | SÍ | SÍ |
Dos soluciones satisfacen a todas las vacas:
- El proyecto 1 se aprueba (satisface a las vacas 1, 3 y 4).
- El proyecto 2 se rechaza (satisface a la vaca 2).
- El proyecto 3 puede aprobarse o rechazarse (por eso hay dos soluciones).
De hecho, son las únicas soluciones, así que la respuesta es esta cadena de tres caracteres:
YN?
Entrada
Lee de la entrada estándar.
- Línea $1$: dos enteros separados por espacios, $N$ y $M$.
- Líneas $2 \ldots M+1$: la línea $i+1$ describe los votos de la vaca $i$ con cuatro campos separados por espacios: entero, voto, otro entero y otro voto, $B_i$, $VB_i$, $C_i$, $VC_i$.
Salida
Escribe en la salida estándar.
- Línea $1$: una cadena de $N$ caracteres, cuyo carácter $i$ es "$Y$" si el proyecto $i$ debe aprobarse, "$N$" si debe rechazarse, o "?" si estos votos no determinan si se aprueba.
Si no hay solución que satisfaga a todas las vacas, imprime una sola línea "IMPOSSIBLE".
Ejemplos
Entrada 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Salida 1
YN?
Autor del problema: Louis Wasserman, 2010