Scontente della guida di Farmer John, le mucche si sono separate dalla fattoria e hanno fondato il primo Continental Cowngress. Secondo il principio «ogni mucca ottiene qualcosa che vuole», hanno scelto questo sistema:
Le $M$ mucche presenti ($1 \leq M \leq 4{,}000$) votano su $N$ proposte di legge ($1 \leq N \leq 1{,}000$). Ognuna vota sì o no (input '$Y$' o '$N$') su esattamente due proposte distinte $B_i$ e $C_i$ ($1 \leq B_i, C_i \leq N$). I voti sono $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) e $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
Le decisioni devono soddisfare almeno un voto di ogni mucca. Se Bessie vota sì alla proposta 1 e no alla 2, ogni soluzione valida deve approvare la 1 o respingere la 2 (o entrambe).
Dati i voti, determina i risultati conformi alle regole. Senza soluzione, stampa "IMPOSSIBLE". Se ce n'è almeno una, mostra per ogni proposta:
- $Y$ se è approvata in ogni soluzione.
- $N$ se è respinta in ogni soluzione.
?se esistono soluzioni che l'approvano e altre che non l'approvano.
Considera i voti seguenti (due per mucca):
Proposte di legge
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Mucca $1$ | SÌ | NO | |
| Mucca $2$ | NO | NO | |
| Mucca $3$ | SÌ | SÌ | |
| Mucca $4$ | SÌ | SÌ |
Due soluzioni soddisfano ogni mucca:
- La proposta 1 è approvata (soddisfa le mucche 1, 3 e 4).
- La proposta 2 è respinta (soddisfa la mucca 2).
- La proposta 3 può essere approvata o respinta (da qui le due soluzioni).
Sono infatti le sole soluzioni, quindi la risposta è questa stringa di tre caratteri:
YN?
Input
Leggi dallo standard input.
- Riga $1$: due interi separati da spazi, $N$ e $M$.
- Righe $2 \ldots M+1$: la riga $i+1$ descrive i voti della mucca $i$ con quattro campi separati da spazi: intero, voto, altro intero e altro voto, $B_i$, $VB_i$, $C_i$, $VC_i$.
Output
Scrivi sullo standard output.
- Riga $1$: una stringa di $N$ caratteri, il cui carattere $i$ è "$Y$" se la proposta $i$ deve essere approvata, "$N$" se deve essere respinta, o "?" se i voti non determinano il risultato.
Se non esiste una soluzione che soddisfi ogni mucca, stampa una sola riga "IMPOSSIBLE".
Esempi
Input 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Output 1
YN?
Autore del problema: Louis Wasserman, 2010