Insatisfeitas com a liderança de Farmer John, as vacas se separaram da fazenda e fundaram o primeiro Continental Cowngress. Com o princípio de que «cada vaca obtém algo que deseja», escolheram este sistema:
As $M$ vacas presentes ($1 \leq M \leq 4{,}000$) votam em $N$ projetos de lei ($1 \leq N \leq 1{,}000$). Cada uma vota sim ou não (entrada '$Y$' ou '$N$') em exatamente dois projetos distintos $B_i$ e $C_i$ ($1 \leq B_i, C_i \leq N$). Os votos são $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) e $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
As decisões devem satisfazer pelo menos um voto de cada vaca. Se Bessie vota sim no projeto 1 e não no 2, toda solução válida deve aprovar o 1 ou rejeitar o 2 (ou ambos).
Dados os votos, determine os resultados conforme as regras. Sem solução, imprima "IMPOSSIBLE". Se houver pelo menos uma, mostre para cada projeto:
- $Y$ se é aprovado em toda solução.
- $N$ se é rejeitado em toda solução.
?se há soluções que o aprovam e outras que não.
Considere os votos abaixo (dois por vaca):
Projetos de lei
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Vaca $1$ | SIM | NÃO | |
| Vaca $2$ | NÃO | NÃO | |
| Vaca $3$ | SIM | SIM | |
| Vaca $4$ | SIM | SIM |
Duas soluções satisfazem todas as vacas:
- O projeto 1 é aprovado (satisfaz as vacas 1, 3 e 4).
- O projeto 2 é rejeitado (satisfaz a vaca 2).
- O projeto 3 pode ser aprovado ou rejeitado (por isso há duas soluções).
Na verdade, essas são as únicas soluções, e a resposta é esta string de três caracteres:
YN?
Entrada
Leia da entrada padrão.
- Linha $1$: dois inteiros separados por espaços, $N$ e $M$.
- Linhas $2 \ldots M+1$: a linha $i+1$ descreve os votos da vaca $i$ em quatro campos separados por espaços: inteiro, voto, outro inteiro e outro voto, $B_i$, $VB_i$, $C_i$, $VC_i$.
Saída
Escreva na saída padrão.
- Linha $1$: uma string de $N$ caracteres, cujo caractere $i$ é "$Y$" se o projeto $i$ deve ser aprovado, "$N$" se deve ser rejeitado, ou "?" se os votos não determinam se é aprovado.
Sem solução que satisfaça todas as vacas, imprima uma única linha "IMPOSSIBLE".
Exemplos
Entrada 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Saída 1
YN?
Autor do problema: Louis Wasserman, 2010