במעבדה של Professor JOI חוקרים $N$ סוגי מינרלים. יש 2 פרוסות מכל סוג של מינרל. בסך הכול יש $2N$ פרוסות, הממוספרות מ־$1$ עד $2N$.

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

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

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

כדי ש־Professor JOI לא יגלה ש־Bitaro גורם לצרות, Bitaro יכול לבצע פעולות אלו לכל היותר $1\,000\,000$ פעמים בסך הכול.

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

פרטי מימוש

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

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

• void Solve(int N)

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

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

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

• int Query(int x)

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

• עליכם לציין את מספר הפרוסה $x$ באמצעות הפרמטר x. עליו לקיים $1 \le x \le 2N$. אחרת, התוכנית שלכם תיחשב כבעלת תשובה שגויה [1].

• אין לקרוא לפונקציה Query יותר מ־$1\,000\,000$ פעמים. אחרת, התוכנית שלכם תיחשב כבעלת תשובה שגויה [2].

• void Answer(int a, int b)

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

• הפרמטרים a ו־b מציינים שהפרוסה ה־$a$ והפרוסה ה־$b$ הן מאותו סוג מינרל. עליהם לקיים $1 \le a \le 2N$ וגם $1 \le b \le 2N$. אחרת, התוכנית שלכם תיחשב כבעלת תשובה שגויה [3]. אם אותו ערך מופיע יותר מפעם אחת בסך הכול בין הערכים של a ו־b, התוכנית שלכם תיחשב כבעלת תשובה שגויה [4]. אם מצוינות פרוסות מסוגים שונים של מינרל, התוכנית שלכם תיחשב כבעלת תשובה שגויה [5].

יש לקרוא לפונקציה Answer בדיוק $N$ פעמים. אם מספר הקריאות לפונקציה Answer אינו $N$ בסיום ביצוע הפונקציה Solve, התוכנית שלכם תיחשב כבעלת תשובה שגויה [6].

הערות חשובות

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

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

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

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

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

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

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

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

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

$$ \begin{array}{ll} N \\ X_1 & Y_1 \\ \vdots \\ X_N & Y_N \end{array} $$

$X_i$ ו־$Y_i$ $(1 \le i \le N)$ מציינים שהפרוסה ה־$X_i$ והפרוסה ה־$Y_i$ הן מאותו סוג מינרל.

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

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

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

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

מגבלות

להגדרת $X_i$ ו־$Y_i$, עיינו בסעיף ״קלט לתוכנית הבדיקה לדוגמה״.

• $1 \le N \le 43\,000$.
• $1 \le X_i \le 2N$ $(1 \le i \le N)$.
• $1 \le Y_i \le 2N$ $(1 \le i \le N)$.
• $X_i \ne X_j$ $(1 \le i < j \le N)$.
• $Y_i \ne Y_j$ $(1 \le i < j \le N)$.
• $X_i \ne Y_j$ $(1 \le i \le N,\ 1 \le j \le N)$.

תתי־משימות

1. (6 נקודות) $N \le 100$.
2. (25 נקודות) $N \le 15\,000$, $1 \le X_i \le N$, $N + 1 \le Y_i \le 2N$ $(1 \le i \le N)$.
3. (9 נקודות) $N \le 15\,000$.
4. (30 נקודות) $N \le 38\,000$.
5. (5 נקודות) $N \le 39\,000$.
6. (5 נקודות) $N \le 40\,000$.
7. (5 נקודות) $N \le 41\,000$.
8. (5 נקודות) $N \le 42\,000$.
9. (10 נקודות) אין מגבלות נוספות.

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

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

קלט 1

4
1 5
2 6
3 4
7 8

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

• קריאה: Solve(4).
• קריאה: Query(1); ערך מוחזר: 1.
• קריאה: Query(2); ערך מוחזר: 2.
• קריאה: Query(5); ערך מוחזר: 2.
• קריאה: Query(2); ערך מוחזר: 1.
• קריאה: Answer(3, 4); ללא ערך מוחזר.
• קריאה: Answer(5, 1); ללא ערך מוחזר.
• קריאה: Answer(8, 7); ללא ערך מוחזר.
• קריאה: Answer(2, 6); ללא ערך מוחזר.