במפעל של JOI Co., Ltd. יש $N$ שולחנות, הממוספרים מ-$0$ עד $N-1$. במפעל יש $N-1$ מסועים, הממוספרים מ-$0$ עד $N-2$. המסוע $i$ ($0\le i\le N-2$) מחבר בין השולחן $A_i$ לשולחן $B_i$. הוא מעביר מוצרים מאחד השולחנות אל האחר. עם זאת, אי אפשר לראות את כיוון ההעברה. אם מתעלמים מכיווני המסועים, כל זוג שולחנות מחובר באמצעות מספר מסועים.

IOI-kun הוא מנהל המפעל. מאחר ששכח את כיוון ההעברה של כל מסוע, הוא יבצע את רצף הפעולות הבא מספר פעמים.

1. הוא בוחר מספר מסועים והופך את כיווני ההעברה של המסועים שנבחרו.
2. הוא בוחר מספר שולחנות ומניח מוצר אחד על כל שולחן שנבחר.

3. עבור כל שולחן שעליו הונח מוצר, אחד הדברים הבאים מתרחש בו־זמנית.

   • אם אין מסוע שמעביר מוצרים מהשולחן הזה, לא קורה דבר.
   • אם יש מסועים שמעבירים מוצרים מהשולחן הזה, המוצר שעליו מועבר באחד מהם. המוצר נעצר ביעד המסוע ולא ינוע עוד.
4. IOI-kun בודק אם יש מוצר אחד או יותר על כל שולחן. אם יש מוצרים על שולחן, הוא לוקח את כולם.
5. עבור כל מסוע שכיוונו נהפך בפעולה 1, IOI-kun הופך שוב את כיוונו. כיוונו חוזר להיות הכיוון המקורי.

IOI-kun רוצה לזהות את הכיוון המקורי של כל מסוע באמצעות ביצוע רצף הפעולות שלעיל לכל היותר 30 פעמים.

כתבו תוכנית שבהינתן מידע על השולחנות המחוברים במסועים, מממשת את האסטרטגיה של IOI-kun לזיהוי הכיוון המקורי של כל מסוע באמצעות ביצוע רצף הפעולות שלעיל לכל היותר 30 פעמים.

פרטי מימוש

עליכם להגיש קובץ אחד.

הקובץ הוא conveyor.cpp. עליו לממש את הפונקציה הבאה. התוכנית צריכה לכלול את conveyor.h באמצעות הוראת קדם־המעבד #include.

ב-conveyor.cpp יש לממש את הפונקציה הבאה.

void Solve(int N, std::vector<int> A, std::vector<int> B)

פונקציה זו נקראת פעם אחת בלבד לכל מקרה בדיקה.

• הפרמטר N הוא מספר השולחנות $N$.
• הפרמטרים A, B הם מערכים באורך $N-1$, המתארים את השולחנות המחוברים במסועים.

התוכנית יכולה לקרוא לפונקציות הבאות.

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

באמצעות פונקציה זו IOI-kun מבצע את הפעולות במפעל.

• הפרמטר x הוא מערך באורך $N-1$. עבור $0\le i\le N-2$, אם x[i] = 1, IOI-kun הופך את כיוון המסוע $i$, ואם x[i] = 0, הוא אינו הופך את כיוונו.
• הפרמטר y הוא מערך באורך $N$. עבור $0\le j\le N-1$, אם y[j] = 1, IOI-kun מניח מוצר על השולחן $j$, ואם y[j] = 0, הוא אינו מניח עליו מוצר.
• יהי z הערך המוחזר מהפונקציה. זהו מערך באורך $N$. עבור $0\le j\le N-1$, אם z[j] = 1, יש מוצר אחד או יותר על השולחן $j$, ואם z[j] = 0, אין עליו מוצר.
• אורך המערך x חייב להיות $N-1$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [1].
• כל איבר במערך x חייב להיות $0$ או $1$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [2].
• אורך המערך y חייב להיות $N$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [3].
• כל איבר במערך y חייב להיות $0$ או $1$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [4].
• אין לקרוא לפונקציה Query יותר מ-30 פעמים. אם היא נקראת יותר מ-30 פעמים, התוכנית תקבל את פסק הדין Wrong Answer [5].

void Answer(std::vector<int> a)

באמצעות פונקציה זו IOI-kun מדווח על הכיוון המקורי של כל מסוע.

• הפרמטר a הוא מערך באורך $N-1$. עבור $0\le i\le N-2$, המסוע $i$ מעביר מוצרים מ-$A_i$ ל-$B_i$ אם a[i] = 0, ומ-$B_i$ ל-$A_i$ אם a[i] = 1.
• אורך המערך a חייב להיות $N-1$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [6].
• כל איבר במערך a חייב להיות $0$ או $1$. אם תנאי זה אינו מתקיים, התוכנית תקבל את פסק הדין Wrong Answer [7].
• אם IOI-kun מדווח על כיוון שגוי של מסוע, התוכנית תקבל את פסק הדין Wrong Answer [8].
• יש לקרוא לפונקציה Answer בדיוק פעם אחת. אם היא נקראת יותר מפעם אחת, התוכנית תקבל את פסק הדין Wrong Answer [9]. אם בעת סיום הפונקציה Solve הפונקציה Answer לא נקראה, התוכנית תקבל את פסק הדין Wrong Answer [10].

הערות חשובות

• התוכנית יכולה לממש פונקציות נוספות לשימוש פנימי או להשתמש במשתנים גלובליים.
• אסור לתוכנית להשתמש בקלט הסטנדרטי או בפלט הסטנדרטי. אסור לה לתקשר עם קבצים אחרים בשום דרך. עם זאת, מותר לה להדפיס מידע לניפוי שגיאות לפלט השגיאות הסטנדרטי.

הידור והרצת בדיקות

ניתן להוריד מאתר התחרות קובץ ארכיון המכיל תוכנית בדיקה לדוגמה לצורך בדיקת התוכנית שלכם. הארכיון מכיל גם קובץ קוד מקור לדוגמה של התוכנית שלכם.

תוכנית הבדיקה לדוגמה נמצאת בקובץ grader.cpp. כדי לבדוק את התוכנית שלכם, שימו את grader.cpp, conveyor.cpp, conveyor.h באותה תיקייה והריצו את הפקודה הבאה להידור. לחלופין, ניתן להריץ את compile.sh שבארכיון.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

כאשר ההידור מצליח, נוצר קובץ ההרצה grader.

שימו לב שתוכנית הבדיקה האמיתית שונה מתוכנית הבדיקה לדוגמה. תוכנית הבדיקה לדוגמה רצה כתהליך יחיד, הקורא נתונים מהקלט הסטנדרטי וכותב תוצאות לפלט הסטנדרטי.

קלט לתוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה קוראת את הנתונים הבאים מהקלט הסטנדרטי.

$$ \begin{gathered} N\\ A_0\quad A_1\quad\cdots\quad A_{N-2}\\ B_0\quad B_1\quad\cdots\quad B_{N-2}\\ C_0\quad C_1\quad\cdots\quad C_{N-2} \end{gathered} $$

עבור $0\le i\le N-2$, מתקיים $C_i=0$ אם המסוע $i$ מעביר מוצרים מהשולחן $A_i$ לשולחן $B_i$. אחרת, $C_i=1$.

פלט של תוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה מדפיסה את המידע הבא לפלט הסטנדרטי (המירכאות נועדו להבהרה).

• אם התוכנית שלכם נמצאה נכונה, מספר הקריאות לפונקציה Query מדווח בצורה „Accepted: 22”.
• אם התוכנית מקבלת סוג כלשהו של תשובה שגויה, תוכנית הבדיקה לדוגמה מדפיסה את סוגו בצורה „Wrong Answer [4]”.

אם התוכנית מקיימת את התנאים לכמה סוגים של תשובה שגויה, תוכנית הבדיקה לדוגמה מדווחת רק על אחד מהם.

בתוכנית הבדיקה לדוגמה, מבין המסועים המעבירים מוצרים מהשולחן שעליו הונח מוצר, המסוע שמעביר את המוצר נבחר באקראי ובהתפלגות אחידה באמצעות מספרים פסאודו־אקראיים, שתוצאותיהם אינן משתנות בין הרצות. כדי לשנות את הזרע של המספרים הפסאודו־אקראיים, הריצו את תוכנית הבדיקה לדוגמה עם מספר שלם כארגומנט הראשון, כך:

./grader 2023

הערות לגבי הבדיקה

בחלק ממקרי הבדיקה תוכנית הבדיקה האמיתית היא אדפטיבית. פירוש הדבר שבתחילה אין לה תשובה קבועה, והיא מגיבה בהתאם לקריאות הקודמות לפונקציה Query. מובטח שקיימת לפחות תשובה אחת שאינה סותרת אף אחת מתגובות תוכנית הבדיקה.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $0\le A_i\le N-1$ ($0\le i\le N-2$).
• $0\le B_i\le N-1$ ($0\le i\le N-2$).
• אם מתעלמים מכיווני המסועים, כל זוג שולחנות מחובר באמצעות מספר מסועים.

תתי־משימות

1. (נקודה אחת) $N=2$.
2. (14 נקודות) $N=30$.
3. (10 נקודות) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$).
4. (75 נקודות) $N=100\,000$.

דוגמה

להלן קלט לדוגמה לתוכנית הבדיקה לדוגמה והקריאות המתאימות לפונקציות.

קלט 1

3
0 2
2 1
1 0

קריאות לפונקציות

Solve(3, [0, 2], [2, 1])

בקריאה הראשונה לפונקציה Query, ערך מוחזר אפשרי נוסף, מלבד [1, 0, 0], הוא [0, 1, 0].

בקריאה השנייה לפונקציה Query, המוצר שעל השולחן $0$ מועבר לשולחן $2$ דרך המסוע $0$ ונעצר שם. שימו לב שמוצר זה לא יועבר לשולחן $1$ דרך המסוע $1$.

שימו לב שקלט דוגמה זה אינו מקיים את המגבלות של אף תת־משימה.

מבין הקבצים שניתן לקבל מאתר התחרות, sample-02.txt מקיים את המגבלות של תת־משימה 1, ו-sample-03.txt מקיים את המגבלות של תת־משימה 2.