Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 2048 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

يواجه بيغي (الذي يدير في أوقات فراغه لجنة بروتوكول الاتصال بين النجوم) معضلةً دقيقةً في العتاد. فشبكة الاتصالات الأحدث، المكوَّنة من $n$ محطات تقوية متصلة بواسطة $(n - 1)$ روابط ألياف بصرية لتشكّل بنية شجرية، أصبحت جاهزةً أخيرًا للنشر. غير أن تشغيل النظام يجب أن يتم بحذر شديد.

تتضمن عملية التفعيل إطلاق نبضات ليزر على طول مسارات محددة. ويُعرَّف المسار بأنه الطريق البسيط الوحيد بين محطتين. وبسبب الخطر الكارثي لظاهرة «تداخل التدفق العكسي الكمومي» — وهي ظاهرة تؤرق محامي اللجنة طوال الليل — يجب الالتزام الصارم بالبروتوكول التالي:

  • يجب إنشاء مسارات الإرسال واحدًا تلو الآخر.
  • لمنع طفرات الطاقة، يجوز لكل مسار يُنشأ حديثًا أن يشترك في محطة واحدة على الأكثر مع مجموعة المحطات التي تم تفعيلها مسبقًا بواسطة أي مسار سابق.

بصورة رسمية، لتكن $S$ مجموعة المحطات المفعَّلة حاليًا. لأي مسار جديد $P$ يتكون من مجموعة محطات $V(P)$، يجب أن يتحقق الشرط $|V(P) \cap S| \le 1$. وبمجرد إطلاق نبضة بنجاح عبر مسار ما، تُعتبر جميع المحطات الواقعة على طول ذلك المسار جزءًا من المجموعة المفعَّلة $S$.

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

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
رسم توضيحي لحالتي الاختبار الأوليين في المثال. لاحظ أنه في الحالة 2، تشترك النبضة الثانية مع الأولى في المحطة $2$ فقط، مما يحقق قاعدة عدم التداخل.

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 10^4$) يشير إلى عدد حالات الاختبار. ولكل حالة اختبار:

يحتوي السطر الأول على عدد صحيح $n$ ($2 \le n \le 3 \times 10^5$)، وهو عدد المحطات في الشبكة.

وفي الأسطر الـ $(n - 1)$ التالية، يحتوي السطر رقم $i$ على عددين صحيحين $u_i$ و $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)، يصفان رابط ألياف بصرية ثنائي الاتجاه بين المحطة $u_i$ والمحطة $v_i$.

من المضمون أن الروابط تشكّل شجرةً وأن مجموع قيم $n$ عبر جميع حالات الاختبار لا يتجاوز $3 \times 10^5$.

الإخراج

لكل حالة اختبار، اطبع الحد الأدنى لعدد المسارات $k$ في السطر الأول. وبعد ذلك، اطبع $k$ أسطر يحتوي كل منها على عددين صحيحين $a_i$ و $b_i$ يمثلان طرفي المسار رقم $i$ في المتتالية. لاحظ أن $a_i$ قد يساوي $b_i$ إذا كان المسار يتكون من محطة واحدة فقط.

إذا وُجدت عدة متتاليات مثلى، فسيتم قبول أي متتالية تتبع بروتوكول عدم التداخل بدقة.

مثال

الإدخال

3
3
1 2
2 3
5
1 2
2 3
2 4
2 5
7
1 2
1 3
2 4
2 5
3 6
3 7

الإخراج

1
1 3
2
4 5
1 3
3
7 7
1 6
4 5

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.