يبحث مختبر الأستاذ JOI في $N$ نوعًا من المعادن. توجد شريحتان من كل نوع من المعادن. يوجد إجمالًا $2N$ شريحة، مرقمة من $1$ إلى $2N$.

ذات يوم، أسقط المساعد Bitaro الصندوق الذي يحتوي على الشرائح الـ $2N$، فلم يعد يعرف أي شريحتين تنتميان إلى النوع نفسه من المعادن.

يمتلك المختبر جهازًا يمكنه عد أنواع المعادن عند إدخال بعض الشرائح فيه، وذلك بقياس الطول الموجي الذي يمتصه كل معدن. يريد Bitaro تحديد الأزواج الـ $N$ التي يتكون كل منها من شريحتين من النوع نفسه، من بين الشرائح الـ $2N$. في البداية، لا توجد أي شريحة داخل الجهاز. يستطيع Bitaro إجراء العمليتين التاليتين:

• إدخال شريحة واحدة في الجهاز، ومعرفة عدد أنواع المعادن الموجودة في الجهاز.
• إخراج شريحة واحدة من الجهاز، ومعرفة عدد أنواع المعادن الموجودة في الجهاز.

حتى لا يكتشف الأستاذ 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$. وإلا، يُحكم على برنامجك بـ Wrong Answer [1].
    • يجب ألا تُستدعى الدالة Query أكثر من $1\,000\,000$ مرة. وإلا، يُحكم على برنامجك بـ Wrong Answer [2].

  • void Answer(int a, int b)

    باستخدام هذه الدالة، تقدم أزواج الشرائح التي تنتمي إلى المعدن نفسه.

    • يمثل المعاملان a وb أن الشريحة رقم $a$ والشريحة رقم $b$ تنتميان إلى النوع نفسه من المعادن. يجب أن يتحقق $1\le a\le 2N$ و$1\le b\le 2N$. وإلا، يُحكم على برنامجك بـ Wrong Answer [3]. إذا ظهرت القيمة نفسها أكثر من مرة ضمن قيم a أو b إجمالًا، يُحكم على برنامجك بـ Wrong Answer [4]. إذا حُددت شريحتان من نوعين مختلفين من المعادن، يُحكم على برنامجك بـ Wrong Answer [5].

  يجب استدعاء الدالة Answer بالضبط $N$ مرة. إذا لم يكن عدد استدعاءات الدالة Answer يساوي $N$ عند انتهاء تنفيذ الدالة Solve، يُحكم على برنامجك بـ Wrong Answer [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، يكتب نوعه على النحو التالي: “Wrong Answer [1]”.

إذا حُكم على برنامجك بعدة أنواع من Wrong Answer، فإن برنامج التصحيح النموذجي يبلغ عن نوع واحد منها فقط.

القيود

راجع قسم «الإدخال لبرنامج التصحيح النموذجي» لتعريف $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

استدعاءات نموذجية