בהינתן עץ לא מושרש עם $n$ צמתים, עליכם להקצות משקל שונה לכל צומת, כך שהמשקלים יהוו תמורה של המספרים מ-$1$ עד $n$.
עבור כל סכמת הקצאה, אנו בוחנים את כל הקטרים של העץ (כלומר, המסלולים הפשוטים הארוכים ביותר בעץ). מבין קטרים אלה, אנו בוחרים את הקוטר בעל סדרת המשקלים הגדולה ביותר לקסיקוגרפית (על ידי סידור משקלי הצמתים לאורך המסלול לפי הסדר והשוואתם לקסיקוגרפית).
מטרתכם היא למזער את הסדר הלקסיקוגרפי של סדרת המשקלים המתאימה ל"קוטר הגדול ביותר לקסיקוגרפית" זה מבין כל סכמות ההקצאה האפשריות.
קלט
מקרה בדיקה יחיד מכיל מספר קבוצות נתונים.
השורה הראשונה של הקלט היא מספר קבוצות הנתונים $T$ ($1 \le T \le 10^5$), המייצג את מספר קבוצות הנתונים במקרה בדיקה זה.
עבור כל קבוצת נתונים, השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 2 \cdot 10^5$) המציין את מספר הצמתים.
$n - 1$ השורות הבאות מכילות כל אחת שני מספרים שלמים $u, v$ ($1 \le u, v \le n$), המייצגים קשת של העץ.
מובטח כי על פני כל הנתונים, $\sum n \le 2 \cdot 10^5$.
פלט
עבור כל קבוצת נתונים, הדפיסו שורה של מספר מספרים שלמים המייצגים את הסדר הלקסיקוגרפי הקטן ביותר האפשרי של הקוטר בעל הסדר הלקסיקוגרפי הגדול ביותר.
דוגמה
קלט
5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 1 4 6 1 2 1 3 2 4 2 5 3 6 8 1 2 2 3 1 4 2 5 3 6 1 7 7 8 10 1 2 2 3 2 4 4 7 4 8 1 5 5 6 6 9 1 10
פלט
3 4 5 1 3 4 2 3 4 5 6 1 2 3 4 5 6 1 3 4 5 6 7 8 1