Unzufrieden mit Farmer Johns Führung haben sich die Kühe von der Farm getrennt und den ersten Continental Cowngress gegründet. Nach dem Prinzip „jede Kuh bekommt etwas, das sie will“ wählen sie folgendes Abstimmungssystem:
Die $M$ anwesenden Kühe ($1 \leq M \leq 4{,}000$) stimmen über $N$ Gesetzesvorlagen ($1 \leq N \leq 1{,}000$) ab. Jede stimmt bei genau zwei verschiedenen Vorlagen $B_i$ und $C_i$ ($1 \leq B_i, C_i \leq N$) mit Ja oder Nein (Eingabe '$Y$' oder '$N$'). Die Stimmen heißen $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) und $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
Die Ergebnisse sollen jeder Kuh bei mindestens einer Stimme entsprechen. Stimmt Bessie für Vorlage 1 und gegen Vorlage 2, muss jede gültige Lösung Vorlage 1 annehmen oder Vorlage 2 ablehnen (oder beides).
Bestimme aus den Stimmen die regelkonformen Ergebnisse. Gibt es keine Lösung, gib "IMPOSSIBLE" aus. Sonst gib für jede Vorlage an:
- $Y$, wenn sie in jeder Lösung angenommen wird.
- $N$, wenn sie in jeder Lösung abgelehnt wird.
?, wenn es sowohl Lösungen mit Annahme als auch mit Ablehnung gibt.
Betrachte folgende Stimmen (zwei pro Kuh):
Vorlagen
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Kuh $1$ | JA | NEIN | |
| Kuh $2$ | NEIN | NEIN | |
| Kuh $3$ | JA | JA | |
| Kuh $4$ | JA | JA |
Zwei Lösungen stellen alle Kühe zufrieden:
- Vorlage 1 wird angenommen (zufrieden sind Kühe 1, 3 und 4).
- Vorlage 2 wird abgelehnt (zufrieden ist Kuh 2).
- Vorlage 3 kann angenommen oder abgelehnt werden (darum gibt es zwei Lösungen).
Dies sind tatsächlich die einzigen Lösungen; die Antwort ist daher diese Zeichenkette aus drei Zeichen:
YN?
Eingabe
Lies von der Standardeingabe.
- Zeile $1$: zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $M$.
- Zeilen $2 \ldots M+1$: Zeile $i+1$ beschreibt Kuh $i$ mit vier durch Leerzeichen getrennten Feldern: ganze Zahl, Stimme, weitere ganze Zahl, weitere Stimme, $B_i$, $VB_i$, $C_i$, $VC_i$.
Ausgabe
Schreibe auf die Standardausgabe.
- Zeile $1$: eine Zeichenkette mit $N$ Zeichen; das $i$-te ist "$Y$", wenn Vorlage $i$ angenommen werden muss, "$N$", wenn sie abgelehnt werden muss, oder "?", wenn die Stimmen das Ergebnis nicht bestimmen.
Wenn keine Lösung alle Kühe zufriedenstellt, gib eine einzelne Zeile "IMPOSSIBLE" aus.
Beispiele
Eingabe 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Ausgabe 1
YN?
Aufgabenautor: Louis Wasserman, 2010