ישנם $N$ איים שבהם חיים בונים, הממוספרים מ־$0$ עד $N-1$. האיים מחוברים באמצעות $N-1$ גשרים דו־כיווניים. אפשר להגיע מכל אי לכל אי אחר באמצעות גשרים. לכל אי מחוברים ישירות לכל היותר $18$ גשרים. בכל אי חי בונה אחד.

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

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

שימו לב שייתכן שזהו האי שבו חי אחד משלושת הבונים.

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

• אתם מציינים שלושה איים $u$, $v$ ו־$w$ ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$), ומבקשים מהבונים החיים באיים $u$, $v$ ו־$w$ לקיים פגישה.
• לאחר מכן תוכלו לראות באיזה אי שלושת הבונים מתאספים.

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

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

פרטי מימוש

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

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

void Solve(int N)

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

• הפרמטר N מייצג את $N$, מספר האיים.

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

int Query(int u, int v, int w)

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

• אתם מציינים את מספרי שלושת האיים $u$, $v$ ו־$w$ באמצעות הפרמטרים u, v ו־w, בהתאמה. עליהם לקיים $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ ו־$v \ne w$. אחרת, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [1].
• אסור לקרוא לפונקציה Query יותר מ־$100\,000$ פעמים. אחרת, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [2].

void Bridge(int u, int v)

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

• הפרמטרים u ו־v מציינים שהאיים $u$ ו־$v$ מחוברים ישירות בגשר.
• אם התנאי $0 \le u < v \le N-1$ אינו מתקיים, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [3].
• אם האיים $u$ ו־$v$ אינם מחוברים ישירות בגשר, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [4].
• אם הפונקציה Bridge נקראת כמה פעמים עם אותם פרמטרים u ו־v, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [5].
• מכיוון שישנם $N-1$ גשרים, יש לקרוא לפונקציה Bridge בדיוק $N-1$ פעמים. אם בסיום ביצוע הפונקציה Solve מספר הקריאות ל־Bridge אינו $N-1$, התוכנית שלכם תיחשב כבעלת תשובה שגויה מסוג Wrong Answer [6].

הערות חשובות

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

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

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

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

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

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

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

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

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

$$ \begin{array}{ll} N \\ A_0 & B_0 \\ \vdots \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$ ו־$B_i$ ($0 \le i \le N-2$) מציינים שהאיים $A_i$ ו־$B_i$ מחוברים ישירות בגשר.

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

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

• אם התוכנית שלכם נחשבת לנכונה, היא כותבת את מספר הקריאות לפונקציה Query, למשל Accepted: 100.
• אם התוכנית שלכם נחשבת כבעלת תשובה שגויה, היא כותבת את סוג השגיאה, למשל Wrong Answer [1].

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

מגבלות

הגדרות $A_i$ ו־$B_i$ מופיעות בסעיף ״קלט לתוכנית הבדיקה לדוגמה״.

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

תתי־משימות

1. (7 נקודות) $N \le 7$.
2. (10 נקודות) $N \le 50$.
3. (12 נקודות) $N \le 300$.

4. (71 נקודות) אין מגבלות נוספות.

5. בתתי־המשימות 1, 2 ו־3, אם התוכנית שלכם נכונה בכל מקרי הבדיקה בתת־המשימה, תקבלו את מלוא הנקודות.

6. בתת־משימה 4, אם התוכנית שלכם נכונה בכל מקרי הבדיקה, הניקוד שלכם יהיה כמפורט להלן, כאשר $X$ הוא המספר המרבי של קריאות לפונקציה Query במקרה בדיקה אחד.
   • 49 נקודות אם $40\,000 < X \le 100\,000$, וכן
   • 71 נקודות אם $X \le 40\,000$.

תקשורת לדוגמה

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

קלט 1

5
0 1
0 2
1 3
1 4

קריאות לדוגמה