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

ملاحظات مهمة

• يمكن لبرنامجك تنفيذ دوال أخرى للاستخدام الداخلي أو استخدام متغيرات عامة.
• يجب ألا يستخدم برنامجك الإدخال القياسي أو الإخراج القياسي. ويجب ألا يتواصل مع ملفات أخرى بأي وسيلة. لكن يمكنه إخراج معلومات تصحيح الأخطاء إلى مجرى الأخطاء القياسي.

الترجمة البرمجية والتشغيل التجريبي

يمكنك تنزيل ملف أرشيف من صفحة المسابقة يحتوي على برنامج تقييم نموذجي لاختبار برنامجك. يحتوي الأرشيف أيضًا على ملف مصدر نموذجي لبرنامجك.

برنامج التقييم النموذجي هو الملف grader.cpp. لاختبار برنامجك، ضع grader.cpp وmeetings.cpp وmeetings.h في المجلد نفسه، ونفذ الأمر التالي لترجمة برامجك.

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

عندما تنجح الترجمة البرمجية، يُنشأ الملف التنفيذي grader.

لاحظ أن برنامج التقييم الفعلي يختلف عن برنامج التقييم النموذجي. يُنفذ برنامج التقييم النموذجي كعملية واحدة تقرأ بيانات الإدخال من الإدخال القياسي وتكتب النتائج إلى الإخراج القياسي.

الإدخال لبرنامج التقييم النموذجي

يقرأ برنامج التقييم النموذجي البيانات التالية من الإدخال القياسي.

$$ \begin{gathered} N \\ A_0\ B_0 \\ \vdots \\ A_{N-2}\ B_{N-2} \end{gathered} $$

يعني $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

استدعاءات المثال