هذه مسألة تفاعلية.

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

بصفتها الحلوى الأكثر شعبية في المتجر، تتطلب حصة مثالية من حليب القشرتين مزج طبقة الكعك العلوية مع طبقة البودينغ السفلية مزجًا تامًا. وفي مملكة البراغيث السحرية هذه، تتشابك طاقات مكونات طبقتَي الحلوى، وتختبئ داخل شبكة معقدة من المدن.

قرر خبيران مخضرمان في صنع الحلوى في المتجر، dacake8 وdapudding8، اختبارك. لقد أخفيا الكعك والبودينغ على الطرق بين المدن، كلًّا على حدة. ولن تتمكن من إتمام حلوى الختام، حليب القشرتين، إلا باستشارتهما وتحديد مدينة متصلة بالمتجر الرئيسي الذي توجد فيه (المدينة 1) عبر طريق يخفي حلوى!

توجد $n$ مدن، ويربط طريق بين كل مدينتين. توجد $n-1$ قطعة كعك، وتقع القطعة رقم $i$ على الطريق الذي يربط المدينة $u_{i,1}$ بالمدينة $v_{i,1}$. وتوجد $n-1$ قطعة بودينغ، وتقع القطعة رقم $i$ على الطريق الذي يربط المدينة $u_{i,2}$ بالمدينة $v_{i,2}$. تشكّل الطرق التي تحتوي على الكعك والطرق التي تحتوي على البودينغ شجرتين، كلٌّ على حدة.

لا تعرف في البداية المواقع المحددة للكعك والبودينغ. يمكنك توجيه ما لا يزيد على $\min(1000,\frac{n\times(n-1)}{2})$ استعلامًا إلى dacake8 وdapudding8:

• تستعلم من 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}$.
• عليك ضمان ألا يتجاوز عدد استدعاءات هذه الدالة $1000$ في كل استدعاء تجريه مكتبة التفاعل للدالة find.

طريقة اختبار البرنامج

ضع 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}$.

إذا كانت الإجابات في جميع استدعاءات find البالغ عددها $t$ صحيحة، تطبع مكتبة التفاعل 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}$.