זוהי בעיה אינטראקטיבית רב-שלבית (multi-pass). זכרו לרוקן את חוצץ הפלט (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$, לקיחת כל קשת היא קבילה, והרמז יכול להיות שרירותי.