توجد دولتان A وB تربطهما علاقات سيئة. تريد A اكتشاف شبكة السكك الحديدية في B لغزوها. أرسلت جواسيس مرارًا، لكنهم كانوا يُقبض عليهم دائمًا قبل الحصول على معلومات مفيدة. لذلك لا تعرف A إلا ما يلي.

• تتكون شبكة B من $N$ محطات مرقمة من $1$ إلى $N$.

• أي محطتين مختلفتين متصلتان مباشرة بسكة أو عبر محطات أخرى متصلة بسكك.

• يوجد مسار واحد بالضبط بين أي محطتين.

• لا توجد سكة تصل محطة بنفسها مباشرة.

بعد إدراك حدود إرسال الجواسيس، تخطط A لرشوة مسؤول رفيع في شركة السكك الحديدية في B للحصول على رسم للشبكة. إرساله مباشرة سيكشف هوية الخائن، لذا سيعدله كما يلي قبل إرساله إلى A.

• يرسم $K$ سكك زائفة. يختار محطتين مختلفتين $a$ و$b$ غير متصلتين مباشرة بسكة في الرسم، ويصلهما بسكة زائفة. يكرر ذلك $K$ مرات.

• يضع علامة خاصة على محطة واحدة.

• أخيرًا، يمحو جميع أرقام المحطات.

يرسل الخائن الرسم الناتج إلى A. ولأن هذه المعلومات وحدها تجعل التعرف عليه بوصفه شبكة B صعبًا، فلن يعلم أحد بتسريب معلومات سرية.

لكي تنجح الخطة، يجب حل المشكلات التالية.

• لا يحتوي الرسم المستلم على أرقام المحطات ولا يبين السكك الحقيقية والزائفة. لا تعرف A إلا المحطة ذات العلامة وأنه أُضيفت $K$ سكك زائفة بالضبط.

• لذلك يجب على المرسل اختيار السكك الزائفة والمحطة المعلّمة بعناية حتى يستطيع المستلم تمييز السكك الحقيقية من الزائفة باستخدام الرسم فقط.

• يجب على المستلم أيضًا فهم طريقة تعديل الرسم واستعادة رسم الشبكة الأصلية.

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

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

عليك تنفيذ الدالتين التاليتين.

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• الوسيط الصحيح N هو عدد محطات B، أي $N$. تمثل كل محطة بعدد صحيح من $1$ إلى $N$ شاملًا الحدين.

• الوسيط الصحيح K هو عدد السكك الزائفة المطلوب إضافتها، أي $K$.

• يسجل الوسيط X رقم المحطة التي ستُعلّم. عند انتهاء الدالة، يجب أن يحتوي على عدد صحيح موجب من $1$ إلى $N$ شاملًا الحدين.

• حجم المصفوفة E هو $N-1$، وهي تمثل شبكة B. وجود الزوج $(a,b)$ في E يعني أن سكة تصل المحطتين $a$ و$b$ مباشرة.

• أعد مصفوفة تحتوي على $K$ أزواج $(a,b)$ تمثل سككًا زائفة بين محطات مختلفة $a$ و$b$. لا يجوز إضافة سكة زائفة بين $a$ و$b$ إذا كانتا متصلتين مسبقًا بسكة حقيقية أو زائفة.

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• الوسيط الصحيح N هو عدد محطات B، أي $N$. تمثل المحطات بأعداد صحيحة من $1$ إلى $N$ شاملًا الحدين. بما أن الأرقام مُحيت أثناء إرسال الرسم، فقد تختلف أرقام هذه الدالة عن الأرقام الحقيقية. تنتج هذه الأرقام بتطبيق تقابل واحد لواحد على أرقام المحطات المستخدمة في encode_map.

• الوسيط الصحيح K هو عدد السكك الزائفة المضافة، أي $K$.

• الوسيط الصحيح X هو رقم المحطة ذات العلامة الخاصة.

• حجم المصفوفة E هو $N+K-1$، وهي تمثل الرسم المرسل إلى A. يعني الزوج $(a,b)$ أن المحطتين $a$ و$b$ متصلتان مباشرة بسكة حقيقية أو زائفة في الرسم. ترتيب عناصر E لا يحمل أي معنى.

• تستعيد هذه الدالة الرسم الأصلي من الرسم الذي أنتجته encode_map. أعد مصفوفة من $N-1$ أزواج $(a,b)$ تحتوي على شبكة B.

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

تحتوي كل حالة اختبار على سيناريو مستقل واحد أو أكثر. في حالة تحتوي على $T$ سيناريوهات، يُنفذ البرنامج الذي يستدعي الدالتين مرتين بالضبط كما يلي.

في التنفيذ الأول:

• تُستدعى encode_map عدد $T$ مرات.

• يخزن نظام التقييم نتائج encode_map.

• لا تُستدعى decode_map.

في التنفيذ الثاني:

• تُستدعى decode_map عدة مرات. في كل استدعاء يُختار سيناريو اعتباطي، ويُستخدم الرسم الذي أنشأته encode_map لذلك السيناريو كإدخال لـ decode_map.

• لا تُستدعى encode_map.

يُحسب زمن التنفيذ واستخدام الذاكرة بجمع التنفيذين.

القيود

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

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

1. ($4$ نقاط) $N \le 4$.

2. ($13$ نقطة) $K=1$.

3. ($11$ نقطة) تتصل كل محطة بسكتين على الأكثر.

4. ($29$ نقطة) يمكن الانتقال من أي محطة إلى أي محطة أخرى عبر $\lfloor N/2 \rfloor$ سكك على الأكثر.

5. ($43$ نقطة) لا توجد قيود إضافية.

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

يُعد الاختبار صحيحًا فقط إذا أنشأت encode_map رسمًا صالحًا واستعادت decode_map الشبكة بصورة صحيحة. إذا احتوت المصفوفة التي تعيدها decode_map على سكة زائفة واحدة ولو فقط، تكون درجة ذلك الاختبار $0$. لا يهم ترتيب عناصر المصفوفتين اللتين تعيدهما الدالتان.

درجة المهمة الفرعية هي أصغر درجة بين جميع اختباراتها.

أمثلة

• اعتبر $N=6$ و$K=1$ والسكك $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$.

يستدعي برنامج التقييم الدالة التالية.

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

يبين الرسم الأيسر شبكة B. إضافة السكة الزائفة $(4,2)$ وتعليم المحطة $1$ يعطيان الرسم الأيمن. هنا تعيد encode_map القيمة [(4, 2)] وتخزن $1$ في X. قد توجد إجابات أخرى.

بعد ذلك، يستدعي برنامج التقييم الدالة التالية. قد يتغير ترتيب عناصر المصفوفة المعطاة في الوسيط الأخير.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

الرسم الذي يمثله الإدخال مبين أدناه. لاحظ أن أرقام المحطات تختلف عن المستخدمة في encode_map.

تعيد الدالة [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]. قد يختلف ترتيب العناصر.

يحقق هذا المثال شروط المهام الفرعية $2$ و$4$ و$5$.

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

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

• السطر $1$: $T$

تليه $T$ كتل، تمثل كل منها سيناريو واحدًا. صيغة كل كتلة كما يلي.

• السطر $1$: $N\ K$

• السطر $1+i$ ($1 \le i \le N-1$): $a_i\ b_i$

يعني الزوج $a_i,b_i$ وجود سكة تصل المحطتين $a_i$ و$b_i$.

لكل سيناريو، يطبع برنامج التقييم التجريبي ما يلي.

• السطر $1$: المصفوفة التي تعيدها encode_map.

• السطر $2$: المصفوفة التي تعيدها decode_map.

قد يختلف برنامج التقييم التجريبي عن المستخدم في التقييم الفعلي.