غير راضية عن قيادة Farmer John، انفصلت الأبقار عن المزرعة وأسست أول Continental Cowngress. وفق مبدأ «كل بقرة تحصل على شيء تريده»، اختارت نظام التصويت التالي:
تصوت $M$ بقرة حاضرة ($1 \leq M \leq 4{,}000$) على $N$ مشروع قانون ($1 \leq N \leq 1{,}000$). تصوت كل بقرة بنعم أو لا (المدخل '$Y$' أو '$N$') على مشروعين مختلفين بالضبط $B_i$ و$C_i$ ($1 \leq B_i, C_i \leq N$). يُسمّى التصويتان $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) و$VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
يجب أن توافق النتائج رغبة كل بقرة في صوت واحد على الأقل. إذا صوتت Bessie بنعم للمشروع 1 ولا للمشروع 2، فإن كل حل صحيح يقر المشروع 1 أو يرفض المشروع 2 (أو كليهما).
من التصويتات حدّد النتائج الموافقة للقواعد. إن لم يوجد حل، اطبع "IMPOSSIBLE". وإن وجد حل واحد على الأقل، اعرض لكل مشروع:
- $Y$ إذا أُقر في كل حل.
- $N$ إذا رُفض في كل حل.
?إذا وجدت حلول تقره وأخرى لا تقره.
انظر إلى التصويتات التالية (اثنان لكل بقرة):
مشاريع القوانين
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| البقرة $1$ | نعم | لا | |
| البقرة $2$ | لا | لا | |
| البقرة $3$ | نعم | نعم | |
| البقرة $4$ | نعم | نعم |
يوجد حلان يرضيان كل الأبقار:
- يُقر المشروع 1 (يرضي الأبقار 1 و3 و4).
- يُرفض المشروع 2 (يرضي البقرة 2).
- يمكن إقرار المشروع 3 أو رفضه (لذلك يوجد حلان).
في الواقع هذان هما الحلان الوحيدان، لذا الإجابة هي السلسلة التالية من ثلاثة محارف:
YN?
الإدخال
اقرأ من الإدخال القياسي.
- السطر $1$: عددان صحيحان مفصولان بمسافة، $N$ و$M$.
- الأسطر $2 \ldots M+1$: يصف السطر $i+1$ تصويتَي البقرة $i$ بأربعة حقول مفصولة بمسافات: عدد صحيح، صوت، عدد صحيح آخر، صوت آخر، $B_i$ و$VB_i$ و$C_i$ و$VC_i$.
الإخراج
اكتب إلى الإخراج القياسي.
- السطر $1$: سلسلة من $N$ محارف، المحرف $i$ هو "$Y$" إذا وجب إقرار المشروع $i$، أو "$N$" إذا وجب رفضه، أو "?" إذا لم تحدد التصويتات نتيجته.
إن لم يوجد حل يرضي كل بقرة، اطبع سطرًا واحدًا "IMPOSSIBLE".
أمثلة
الإدخال 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
الإخراج 1
YN?
مؤلف المسألة: Louis Wasserman, 2010