هذه مسألة تفاعلية متعددة المراحل (multi-pass, interactive problem). تذكّر تفريغ مخزن الإخراج المؤقت (flush) بعد كل عملية طباعة. لتفريغ الإخراج، يمكنك استخدام:

• fflush(stdout) أو cout.flush() في C/C++؛
• System.out.flush() في Java و Kotlin؛
• sys.stdout.flush() في Python.

مفهوم اللعبة، برسم توضيحي من ChatGPT.

في لعبة المطابقة الفورية (online matching) الكلاسيكية، يتم كشف حواف البيان واحدةً تلو الأخرى. في كل مرة تُعرض فيها حافة، يجب عليك أن تقرر فورًا وبشكل لا رجعة فيه ما إذا كنت ستدرجها في مطابقتك أم لا. هدفك هو ضمان عدم اشتراك أي حافتين مختارتين في رأس واحد مع تعظيم إجمالي عدد الحواف المختارة.

أنت عالم حاسوب طموح متعطش للشهرة. وكما تعلم جيدًا، فإن إيجاد مطابقة عظمى في الوضع الفوري مستحيل إثباتًاباحتمالٍ عالٍ — حتى لأبسط فئات البيانات مثل البيانات ثنائية التجزئة. ولكن حيث يرى الآخرون حاجزًا أساسيًا، ترى أنت فرصةً للمجد. اليوم، تدّعي أنك قد حللت المسألة المفتوحة منذ أمد طويل للأشجار، وأنت مستعد للكشف عن خوارزميتك الثورية للعالم.

هناك مشكلة واحدة فقط: بالأمس، اكتشفت خطأً في برهانك، ولا تزال لا تملك أي فكرة عن كيفية إصلاحه. ولأنك لا ترغب في التخلي عن الأضواء، قررت تحويل عرضك التوضيحي إلى عرض سحري — إذ سيقوم مساعدك المختبئ خلف الكواليس بإرسال تلميح صغير حول الشجرة بأكملها المكوَّنة من $n$ رؤوس قبل بدء اللعبة.

كانت خطتك الأصلية بسيطة: أن يرسل مساعدك الإجابة عن كل استعلام حافة مباشرةً. ولهذا الغرض، قمت بتركيب سماعة أذن سرية قادرة على استقبال سلسلة ثنائية واحدة طولها $(n - 1)$. لكن الجمهور يشكك في «إنجازك». ولمنع أي خدعة مرتبة مسبقًا، يطالبون بأن تُعرض الحواف بترتيب عشوائي منتظم — ترتيب لا يمكنك أنت ولا مساعدك التنبؤ به أو التحكم فيه.

المسرح جاهز، والأضواء مسلطة عليك. أثبت ادعاءك الآن — دون تغيير القناة.

بروتوكول التفاعل

يتم تنفيذ حلك مرتين في كل اختبار. في جولة prepare، سيعمل حلك بدور المساعد. وفي جولة play، سيعمل حلك بدورك أنت، الساحر. وفي كلتا الجولتين، سيتم تقييم حلك كإجراء تفاعلي.

جولة التحضير (Prepare Round)

يحتوي السطر الأول من الإدخال على الكلمة prepare. ويحتوي السطر الثاني على عدد صحيح $n$ ($2 \le n \le 500$) — وهو عدد الرؤوس. وتحتوي الأسطر الـ $(n - 1)$ التالية في كلٍّ منها على عددين صحيحين $u$ و $v$ ($1 \le u, v \le n$، $u < v$)، يمثلان حافة غير موجهة بين $u$ و $v$ في الشجرة.

يجب أن تطبع سطرًا واحدًا يحتوي على سلسلة ثنائية $s$ طولها $(n - 1)$ بالضبط وتتكون من المحرفين 0 و 1 فقط. هذه هي السلسلة التي تُرسل إلى جولة play الثانية. إذا لم يتوافق إخراجك مع التنسيق المطلوب، فستحصل على حكم Wrong Answer.

جولة اللعب (Play Round)

سيتم إعادة تشغيل حلك من أجل جولة play.

يحتوي السطر الأول على الكلمة play. ويحتوي السطر الثاني على العدد الصحيح $n$. ويحتوي السطر الثالث على السلسلة الثنائية $s$ تمامًا كما طبعتها في جولة prepare.

بعد ذلك، تبدأ اللعبة بـ $(n - 1)$ أدوار. في كل دور، سيتم تزويدك بسطر يحتوي على عددين صحيحين $u$ و $v$ ($1 \le u, v \le n$، $u < v$). وكرَدّ، يجب أن تطبع سطرًا واحدًا يحتوي إما على take أو ignore. سيتم تقديم جميع الحواف الموجودة في الجولة الأولى مرة واحدة بالضبط، ويتم اختيار ترتيب الحواف عشوائيًا بانتظام من بين $(n - 1)!$ تبديلًا ممكنًا.

عند وجود إخراج بتنسيق غير صالح، ستنتهي اللعبة فورًا دون مزيد من المعلومات من المتفاعل.

تقييم الصحة

لتكن $M$ مجموعة الحواف التي يأخذها حلك. يُعتبر الحل مقبولًا إذا لم يكن هناك أي رأس متصل بأكثر من حافة مأخوذة واحدة وكان $|M| = |M^*|$، حيث $M^*$ هي المطابقة العظمى للبيان.

يوجد $50$ اختبارًا بالضبط، باستثناء اختبارات المثال. ولكي تجتاز المسألة، يجب أن يكون حلك صحيحًا في جميع الاختبارات بما في ذلك اختبارات المثال.

من المضمون أن جميع عمليات الخلط ثابتة قبل استلام إخراج الحل. العشوائية ثابتة لكل اختبار، ويتم تنفيذها عن طريق تثبيت البذرة (seed) لمولد الأعداد شبه العشوائية.

يتم توفير أداة اختبار لمساعدتك في تطوير حلك واختباره.

مثال

المثال 1، المرحلة 1

الإدخال

prepare
3
1 2
1 3

الإخراج

00

المثال 1، المرحلة 2

الإدخال

play
3
00
1 3

1 2

الإخراج

take

ignore

شرح المثال 1

بما أن $|M^*| = 1$، فإن أخذ أي حافة يُعد مقبولًا، ويمكن أن يكون التلميح اختياريًا.