تتساقط الثلوج في الشتاء في كثير من مناطق روسيا. توجد في روسيا $N$ مدينة مرقمة من $0$ إلى $N-1$، و$N-1$ طريقًا مرقمة من $0$ إلى $N-2$. يربط الطريق $i$ ($0 \le i \le N-2$) بين مدينتين مختلفتين $A_i,B_i$ ($0 \le A_i < B_i \le N-1$) في الاتجاهين. ويمكن الانتقال بين أي مدينتين مختلفتين في روسيا عبر بعض الطرق.

تختلف حالة تساقط الثلوج على كل طريق من يوم إلى آخر. في أي يوم، إما أن يكون الثلج متساقطًا على الطريق أو لا يكون كذلك. ولا تتغير هذه الحالة خلال اليوم الواحد.

تعمل Anya وBoris في هيئة النقل الروسية. تعمل Anya في قسم إدارة معلومات الطرق، ويعمل Boris في قسم الإجابة عن أسئلة المواطنين. يسأل المواطن عن أقل عدد من الطرق التي تتساقط عليها الثلوج والتي لا بد من المرور بها للانتقال من المدينة $0$، عاصمة روسيا، إلى مدينة أخرى معينة. عادةً يتواصل Boris مع Anya بعد تلقي السؤال، ثم يجيب المواطن.

ستُقام في روسيا بطولة عالمية للبرمجة تستمر $Q$ يومًا. ومن المتوقع أن يصعب على Anya وBoris التواصل مباشرة بسبب ازدحام خطوط الاتصال أثناء البطولة. لذلك قررا التواصل بالطريقة التالية.

• تتلقى Anya معلومات تساقط الثلوج لذلك اليوم في بداية اليوم، وترسل بيانات إلى خادم وسيط.
• عندما يتلقى Boris سؤالًا من مواطن، يجيب عنه بالتواصل مع الخادم الوسيط.

لكن تواصلهما يخضع للقيود التالية.

• سعة الخادم الوسيط هي $L=1\,000$ بت. ولا تستطيع Anya تخزين أكثر من $L$ بت من المعلومات فيه.
• تُهيأ جميع البيانات المخزنة في الخادم الوسيط إلى $0$ في بداية كل يوم.
• يستطيع Boris قراءة بت واحد يحدده في كل تواصل مع الخادم الوسيط.
• يمكن لـBoris التواصل مع الخادم الوسيط $20$ مرة على الأكثر لكل سؤال للإجابة عنه.

أنت تعرف مدير هيئة النقل، وقد أُسندت إليك مهمة ابتكار استراتيجية لـAnya وBoris.

تسميات الشكل: Anya؛ الخادم الوسيط؛ السعة $L$ بت؛ حتى $20$ بت لكل سؤال؛ Boris؛ معلومات تساقط الثلوج؛ المواطنون.

المهمة

اكتب برنامجًا ينفذ استراتيجية لـAnya وBoris تتيح الإجابة الصحيحة عن أسئلة المواطنين.

تفاصيل التنفيذ

يجب عليك تسليم ملفين مكتوبين بلغة البرمجة نفسها.

اسم الملف الأول Anya.c أو Anya.cpp. ينفذ هذا الملف استراتيجية Anya، ويجب أن ينفذ الروتينين التاليين. يجب أن يتضمن البرنامج Anyalib.h.

• void InitAnya(int N, int A[], int B[])

تُستدعى هذه الدالة مرة واحدة فقط لكل حالة اختبار.

• المعامل N يمثل عدد المدن.

• المعاملان A[] وB[] متتاليتان طول كل منهما $N-1$، وتمثلان اتصالات الطرق. العنصران A[i] وB[i] ($0 \le i \le N-2$) عددان صحيحان يشيران إلى أن الطريق $i$ يربط المدينتين A[i] وB[i] في الاتجاهين، ويحققان $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• void Anya(int C[])

تُستدعى هذه الدالة $Q$ مرة بعد استدعاء InitAnya. وهي تمثل تحديد Anya لسلسلة البتات التي ستخزنها في الخادم الوسيط بعد تحديث معلومات تساقط الثلوج على الطرق في بداية اليوم.

• المعامل C[] متتالية طولها $N-1$ تمثل معلومات تساقط الثلوج على الطرق. العنصر C[i] ($0 \le i \le N-2$) عدد صحيح يساوي 0 أو 1 ويمثل حالة الطريق $i$: تعني C[i] = 1 أن الثلج يتساقط على الطريق $i$، وتعني C[i] = 0 أنه لا يتساقط عليه.

يمكن استدعاء الدالة التالية داخل Anya.

• void Save(int place, int bit)

تمثل هذه الدالة عملية تخزين Anya لبت في الخادم الوسيط.

• المعامل place يمثل موضع كتابة البت، ويجب أن يكون عددًا صحيحًا بين $0$ و$L-1$ شاملًا الطرفين. إذا استُدعيت الدالة بقيمة خارج هذا النطاق، تُحكم إجابة خاطئة [1]. كذلك، لا يجوز استدعاؤها أكثر من مرة بالمعامل place نفسه ضمن كل استدعاء لـAnya. إذا استُدعيت مرتين بالمعامل نفسه، تُحكم إجابة خاطئة [2].
• المعامل bit عدد صحيح يمثل البت المراد كتابته، ويجب أن يساوي 0 أو 1. إذا استُدعيت الدالة بقيمة أخرى، تُحكم إجابة خاطئة [3].

بعد استدعاء Save، يصبح محتوى البت ذي الموضع place في الخادم الوسيط هو bit.

إذا حُكم على استدعاء Save بأنه إجابة خاطئة، ينتهي البرنامج فورًا.

مباشرة قبل استدعاء Anya، تُهيأ جميع بتات الخادم الوسيط حتمًا إلى $0$. أي إن المواضع التي لا تُجرى عليها عملية تخزين بواسطة Save تحتوي على $0$ عند انتهاء Anya.

اسم الملف الثاني Boris.c أو Boris.cpp. ينفذ هذا الملف استراتيجية Boris، ويجب أن ينفذ الروتينين التاليين. يجب أن يتضمن البرنامج Borislib.h.

• void InitBoris(int N, int A[], int B[])

تُستدعى هذه الدالة مرة واحدة فقط لكل حالة اختبار.

• المعامل N يمثل عدد المدن.

• المعاملان A[] وB[] متتاليتان طول كل منهما $N-1$، وتمثلان اتصالات الطرق. العنصران A[i] وB[i] ($0 \le i \le N-2$) عددان صحيحان يشيران إلى أن الطريق $i$ يربط المدينتين A[i] وB[i] في الاتجاهين، ويحققان $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• int Boris(int city)

تُستدعى هذه الدالة عدة مرات بعد استدعاء InitBoris. وهي تمثل تصرف Boris عند الإجابة عن سؤال مواطن.

• المعامل city يمثل سؤال المواطن، وهو عدد صحيح بين $1$ و$N-1$ شاملًا الطرفين. يعني ذلك أن المواطن يسأل عن أقل عدد من الطرق التي تتساقط عليها الثلوج والتي لا بد من المرور بها للانتقال من المدينة $0$ إلى المدينة city.
• يجب أن تعيد Boris عددًا صحيحًا بين $0$ و$N-1$ شاملًا الطرفين، وهو إجابة سؤال المواطن. إذا أعادت عددًا خارج هذا النطاق، تُحكم إجابة خاطئة [4]. وإذا كانت الإجابة غير صحيحة، تُحكم إجابة خاطئة [7].

يمكن استدعاء الدالة التالية داخل Boris.

• int Ask(int place)

تمثل هذه الدالة عملية قراءة Boris لبت من الخادم الوسيط.

• المعامل place يمثل موضع البت المراد قراءته، ويجب أن يكون عددًا صحيحًا بين $0$ و$L-1$ شاملًا الطرفين. إذا استُدعيت الدالة بقيمة خارج هذا النطاق، تُحكم إجابة خاطئة [5].

القيمة التي تعيدها Ask عدد صحيح يمثل محتوى البت ذي الموضع place في الخادم الوسيط، وهي 0 أو 1. كذلك، لا يجوز استدعاء Ask أكثر من $20$ مرة ضمن كل استدعاء لـBoris. إذا تجاوز عدد الاستدعاءات $20$، تُحكم إجابة خاطئة [6].

إذا حُكم على استدعاء Ask بأنه إجابة خاطئة، ينتهي البرنامج فورًا.

إجراءات التقييم

يجري التقييم وفق الخطوات التالية. إذا حُكم بإجابة خاطئة، ينتهي البرنامج في تلك اللحظة.

1. تُستدعى InitAnya ثم InitBoris مرة واحدة لكل منهما بهذا الترتيب لتزويدهما بمعلومات الطرق.

2. تُنفذ العمليات التالية بالترتيب لكل $i=1,\ldots,Q$.

   • (a) تُستدعى Anya مرة واحدة فقط. يمثل ذلك تحديد Anya لسلسلة البتات التي ستخزنها في الخادم الوسيط بعد تحديث معلومات تساقط الثلوج في بداية اليوم.
   • (b) تُستدعى Boris عدد $D_i$ من المرات، حيث $D_i$ هو عدد أسئلة المواطنين في اليوم $i$. معامل الاستدعاء $j$ ($1 \le j \le D_i$) هو $R_{ij}$ ($1 \le R_{ij} \le N-1$). إذا لم تساوِ القيمة التي تعيدها Boris في الاستدعاء $j$ أقل عدد من الطرق التي تتساقط عليها الثلوج والتي يجب المرور بها للانتقال من المدينة $0$ إلى المدينة $R_{ij}$، تُحكم إجابة خاطئة.

3. إذا لم تُحكم إجابة خاطئة في أي وقت، تُحكم الإجابة صحيحة.

ملاحظات مهمة

• تُقاس مدة التنفيذ والذاكرة المستخدمة في الخطوتين (1) و(2) من «إجراءات التقييم». إذا كانت الإجابة صحيحة، فإن Anya تُستدعى إجمالًا $Q$ مرة، وتُستدعى Boris إجمالًا $D_1+\cdots+D_Q$ مرة في الخطوة (2).
• لا تستطيع Anya ولا Boris معرفة قيم $D_1,\ldots,D_Q$.
• لا تُعطى الدالة Boris معلومات تبين متى حدّثت الدالة Anya البيانات المخزنة في الخادم الوسيط.
• يمكنك تنفيذ روتينات أخرى للاستخدام الداخلي أو التصريح بمتغيرات عامة. لكن البرنامجين المقدمين يُربطان مع برنامج التقييم في ملف تنفيذي واحد، ولذلك يجب التصريح بجميع المتغيرات العامة والروتينات الداخلية في كل ملف (باستثناء InitAnya وAnya وInitBoris وBoris) باستخدام static لتجنب التعارض مع الملفات الأخرى. أثناء التقييم، يُنفذ البرنامج في عمليتين منفصلتين، إحداهما لجانب Anya والأخرى لجانب Boris، لذا لا يمكن مشاركة المتغيرات العامة بين الجانبين.
• يجب ألا يتواصل برنامجك بأي طريقة مع الإدخال القياسي أو الإخراج القياسي أو أي ملفات أخرى.

الترجمة والتنفيذ

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

يتكون برنامج التقييم التجريبي من ملف واحد هو grader.c أو grader.cpp. إذا كان برنامجاك هما Anya.c وBoris.c، أو Anya.cpp وBoris.cpp، فنفذ الأمر المناسب التالي لاختبارهما.

• في حالة C:

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• في حالة C++:

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

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

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

نظرة عامة على برنامج التقييم التجريبي

يستدعي برنامج التقييم التجريبي الدوال وفق «إجراءات التقييم».

انتبه إلى أن النقطة التالية تختلف عن سلوك برنامج التقييم الفعلي.

• لا يفحص برنامج التقييم التجريبي حالة الإجابة الخاطئة [7]، بل يطبع بدلًا من ذلك القيمة التي تعيدها Boris لكل سؤال.

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

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

• يحتوي السطر الأول على عدد صحيح $N$، وهو عدد المدن.
• يحتوي السطر $i+1$ ($0 \le i \le N-2$) من الأسطر $N-1$ التالية على عددين صحيحين $A_i,B_i$ مفصولين بمسافة. يعني ذلك أن الطريق $i$ يربط المدينة $A_i$ والمدينة $B_i$ في الاتجاهين.
• يحتوي السطر التالي على عدد صحيح $Q$، ويعني أن البطولة تستمر $Q$ يومًا.
• يحتوي السطر $i$ ($1 \le i \le Q$) من الأسطر $Q$ التالية على سلسلة $S_i$ طولها $N-1$ وعلى $D_i+1$ عددًا صحيحًا مفصولة بمسافات. تمثل $S_i$ معلومات تساقط الثلوج في اليوم $i$: إذا كان الحرف $j+1$ من اليسار ($0 \le j \le N-2$) هو 1، فالثلج يتساقط على الطريق $j$؛ وإذا كان 0، فلا يتساقط عليه. أول الأعداد الصحيحة $D_i+1$ هو $D_i$، وتليه الأعداد $R_{i1},\ldots,R_{iD_i}$. ويعني ذلك أن السؤال $j$ ($1 \le j \le D_i$) في اليوم $i$ يتعلق بأقل عدد من الطرق التي تتساقط عليها الثلوج والتي يجب المرور بها للانتقال من المدينة $0$ إلى المدينة $R_{ij}$.

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

يطبع برنامج التقييم التجريبي المعلومات التالية إلى الإخراج القياسي (لا تُطبع علامات الاقتباس فعليًا).

• إذا حُكم بإجابة خاطئة أثناء التنفيذ، يُطبع نوعها مثل Wrong Answer [1]، وينتهي التنفيذ.
• إذا لم تُحكم إجابة خاطئة في جميع استدعاءات Boris البالغ عددها $D_i$، التي تلي الاستدعاء $i$ ($1 \le i \le Q$) لـAnya، تُطبع عندئذ $D_i$ أعداد صحيحة في سطر واحد مفصولة بمسافات. العدد $j$ ($1 \le j \le D_i$) منها هو القيمة التي تعيدها $\mathrm{Boris}(R_{ij})$.

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

القيود

تستوفي جميع بيانات الإدخال الشروط التالية.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• يمكن الانتقال بين أي مدينتين مختلفتين عبر بعض الطرق.

المهام الفرعية

المهمة الفرعية 1 [15 نقطة]

• $N \le 20$.

المهمة الفرعية 2 [5 نقاط]

• $N \le 100$.

المهمة الفرعية 3 [35 نقطة]

تستوفى الشروط التالية.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

المهمة الفرعية 4 [45 نقطة]

لا توجد قيود إضافية.

أمثلة

فيما يلي مثال على الإدخال الذي يقرؤه برنامج التقييم التجريبي، ومثال على استدعاءات الدوال المقابلة له.

الإدخال 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

مثال على استدعاءات الروتينات

ملاحظة

انتبه إلى أن استدعاءات الدوال في هذا المثال ليست بالضرورة ذات معنى.

المعاملات الممررة إلى InitAnya(...) وInitBoris(...) والاستدعاءين الأول والثاني لـAnya(...) هي كما يلي، على الترتيب.