פיגי (שבזמנו הפנוי מנהל את נציבות פרוטוקול הקישוריות הבין-כוכבית) ניצב בפני דילמת חומרה עדינה. רשת התקשורת החדשה ביותר, המורכבת מ-$n$ תחנות ממסר המחוברות באמצעות $(n - 1)$ קישורי סיבים אופטיים ליצירת מבנה עץ, מוכנה סוף-סוף לפריסה. עם זאת, יש להפעיל את המערכת בזהירות מרבית.
תהליך ההפעלה כולל שיגור פולסי לייזר לאורך מסלולים מסוימים. מסלול מוגדר כנתיב הפשוט היחיד בין שתי תחנות. בשל הסיכון הקטסטרופלי של "התאבכות זרימה-חוזרת קוונטית" — תופעה שמדירה שינה מעיני עורכי הדין של הנציבות — יש להקפיד בקפדנות על הפרוטוקול הבא:
- יש להקים את מסלולי השידור בזה אחר זה.
- כדי למנוע קפיצות מתח, כל מסלול שמוקם חדש רשאי לחלוק לכל היותר תחנה אחת עם קבוצת התחנות שכבר הופעלו על ידי מסלול קודם כלשהו.
באופן פורמלי, תהי $S$ קבוצת התחנות המופעלות כעת. עבור כל מסלול חדש $P$ המורכב מקבוצת תחנות $V(P)$, חייב להתקיים התנאי $|V(P) \cap S| \le 1$. ברגע שמסלול משוגר בהצלחה, כל התחנות לאורך אותו מסלול נחשבות לחלק מהקבוצה המופעלת $S$.
משימתכם, אם תבחרו לקבל אותה, היא למצוא את המספר המינימלי של פולסי לייזר הדרושים להפעלת כל תחנה ברשת כולה ולספק סדרה אחת כזו של מסלולים כדי להניח את דעתה של המחלקה המשפטית.

איור של שני מקרי הבדיקה הראשונים בדוגמה. שימו לב שבמקרה 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