Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 2048 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

פיגי (שבזמנו הפנוי מנהל את נציבות פרוטוקול הקישוריות הבין-כוכבית) ניצב בפני דילמת חומרה עדינה. רשת התקשורת החדשה ביותר, המורכבת מ-$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.