זוהי בעיה אינטראקטיבית.

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

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

שני אמני הקינוחים הוותיקים בחנות — dacake8 ו־dapudding8 — החליטו לבחון אתכם. הם הסתירו את העוגה ואת הפודינג, כל אחד בנפרד, בדרכים שבין הערים. רק אם תיוועצו בהם ותזהו במדויק עיר המחוברת לחנות הראשית שבה אתם נמצאים (עיר $1$) בדרך שמסתתר בה קינוח, תוכלו להשלים בהצלחה את קינוח הסיום הזה, חלב בעל שני קרומים!

יש $n$ ערים, ובין כל זוג ערים יש דרך. יש $n-1$ חתיכות עוגה; החתיכה ה־$i$ נמצאת בדרך המחברת בין העיר $u_{i,1}$ לעיר $v_{i,1}$. יש $n-1$ חתיכות פודינג; החתיכה ה־$i$ נמצאת בדרך המחברת בין העיר $u_{i,2}$ לעיר $v_{i,2}$. הדרכים שבהן יש עוגה והדרכים שבהן יש פודינג יוצרות שני עצים, בהתאמה.

בתחילה אינכם יודעים את המיקומים המדויקים של העוגה ושל הפודינג. תוכלו להפנות ל־dacake8 ול־dapudding8 לכל היותר $\min(1000,\frac{n\times(n-1)}{2})$ שאילתות:

• בשאילתה ל־dacake8 ול־dapudding8 מציינים את העיר $u$ ואת העיר $v$; בתחילה הרב־קבוצה $S$ ריקה.
  • dacake8 יוצא מהעיר $u$, עובר במסלול המורכב מדרכים שבהן יש עוגה ומגיע לעיר $v$, ומוסיף ל־$S$ את מספרי הערים שבהן עבר.
  • dapudding8 יוצא מהעיר $u$, עובר במסלול המורכב מדרכים שבהן יש פודינג ומגיע לעיר $v$, ומוסיף ל־$S$ את מספרי הערים שבהן עבר.
• ספריית האינטראקציה מחזירה את הרב־קבוצה $S$.

אתם נמצאים בעיר $1$. לאחר סיום השאילתות, עליכם לציין עיר $u$ כך שבדרך המחברת בין העיר $1$ לעיר $u$ יש קינוח מסוג כלשהו.

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

פרטי מימוש

המתחרים אינם צריכים, ואף אינם אמורים, לממש את הפונקציה main.

על המתחרים לכלול את קובץ הכותרת milk.h בקובץ המקור milk.cpp ולממש את שתי הפונקציות הבאות:

void init(int c, int t);

• $c,t$ מציינים את מספר תת־המשימה ואת מספר מקרי הבדיקה, בהתאמה. $id=0$ מציין שקובץ הבדיקה הוא דוגמה.
• לכל קובץ בדיקה, ספריית האינטראקציה תקרא לפונקציה הזאת בדיוק פעם אחת בתחילת ריצת התוכנית.

int find(int c, int n);

• $c,n$ מציינים את מספר תת־המשימה ואת מספר הערים, בהתאמה.
• על הפונקציה להחזיר מספר שלם חיובי $u$, המציין עיר $u$ כך שבדרך המחברת בין העיר $1$ לעיר $u$ יש קינוח מסוג כלשהו.
• לכל קובץ בדיקה, ספריית האינטראקציה תקרא לפונקציה הזאת בדיוק $t$ פעמים.

המתחרים יכולים לבצע שאילתה באמצעות קריאה לפונקציה הבאה:

std::vector<int>query(int u, int v);

• $u,v$ מציינים שתי ערים $u$ ו־$v$.
• על המתחרים להבטיח כי $1\le u,v\le n$ וכן $u\ne v$.
• הפונקציה מחזירה את הרב־קבוצה $S$, שמשמעותה מפורטת בתיאור הבעיה.
• אם גודל הרב־קבוצה $S$ הוא $m$, מתקיים $1\le S_i\le n$ וכן $S_0\le S_1\le \ldots \le S_{m-1}$.
• על המתחרים להבטיח שבכל קריאה של ספריית האינטראקציה ל־find, מספר הקריאות לפונקציה הזאת לא יעלה על $1000$.

בדיקת התוכנית

שימו את milk.cpp, את milk.h ואת grader.cpp מהקבצים המצורפים באותה תיקייה, והדרו באמצעות C++17:

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

עבור קובץ ההרצה milk שנוצר בהידור:

השורה הראשונה בקלט של ספריית האינטראקציה מכילה שני מספרים שלמים אי־שליליים $id,t$, המציינים את מספר קובץ הבדיקה ואת מספר מקרי הבדיקה, בהתאמה.

לכל מקרה בדיקה, השורה הראשונה מכילה מספר שלם חיובי $n$, המציין את מספר הערים. כל אחת מהשורות $2\sim n$ מכילה שני מספרים שלמים חיוביים $u_{i,1}$, $v_{i,1}$; לאחריהן, כל אחת מ־$n-1$ השורות הבאות מכילה שני מספרים שלמים חיוביים $u_{i,2}$, $v_{i,2}$.

אם התשובות בכל $t$ הקריאות ל־find נכונות, ספריית האינטראקציה תדפיס בשורה הראשונה Correct! ובשורה השנייה Max queries used: Q, כאשר $Q$ מציין את מספר הקריאות המרבי ל־query על פני כל מקרי הבדיקה. אם לפחות תשובה אחת שגויה, יודפס Wrong answer.; אם קריאה לממשק אינה תקינה, סיבת השגיאה תיכתב גם לזרם השגיאות התקני.

דוגמאות

קלט 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

פלט 1

Correct!
Max queries used: 28

הסבר

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

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

במקרה הבדיקה הראשון, העצים שנוצרים מהדרכים שבהן יש עוגה ופודינג נראים כך:

במקרה הבדיקה השני, העצים שנוצרים מהדרכים שבהן יש עוגה ופודינג נראים כך:

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

מגבלות

תכונה מיוחדת $\text{A}$: מיקומי העוגה והפודינג נוצרים באקראי לחלוטין.

תכונה מיוחדת $\text{B}$: מובטח שקיימת תשובה אפשרית יחידה.

תכונה מיוחדת $\text{C}$: אם משרישים בעיר $1$ את שני העצים שנוצרים מהדרכים שבהן יש עוגה ופודינג, ומכל עיר מוסיפים קשת מכוונת לעיר ההורה שלה בכל אחד משני העצים, הגרף המכוון שמתקבל הוא DAG.

תכונה מיוחדת $\text{D}$: אם משרישים בעיר $2$ את שני העצים שנוצרים מהדרכים שבהן יש עוגה ופודינג, ומכל עיר מוסיפים קשת מכוונת לעיר ההורה שלה בכל אחד משני העצים, הגרף המכוון שמתקבל הוא DAG.

תכונה מיוחדת $\text{E}$: מיקומי הפודינג נוצרים באקראי לחלוטין. מיקומי העוגה אינם תלויים במיקומי הפודינג.

תכונה מיוחדת $\text{F}$: שני העצים שנוצרים מהדרכים שבהן יש עוגה ופודינג הם שתי שרשראות, ועיר $1$ היא ראש השרשרת בשתיהן.

בבעיה זו, יצירת עץ באקראי מוגדרת באמצעות סדרת Prufer אקראית.

ניקוד

אם התשובה שמחזירה find אינה נכונה, או שהפרמטרים של query אינם תקינים, מכפיל הניקוד של קובץ הבדיקה הוא $0$.

בתת־המשימות $1,2,3$, אם מספר השאילתות עולה על $\frac{n\times(n-1)}{2}$, מכפיל הניקוד של קובץ הבדיקה הוא $0$; אחרת, מכפיל הניקוד הוא $1$.

בתת־המשימות $4\sim 15$, נסמן ב־$Q$ את מספר הקריאות המרבי ל־query על פני כל מקרי הבדיקה. מכפיל הניקוד $f(Q)$ מחושב לפי הטבלה הבאה:

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

מגבלת זמן: $20\ \mathrm{s}$.

מגבלת זיכרון: $512\ \mathrm{MiB}$.