נתון עץ עם $n$ קודקודים, כאשר כל קודקוד צבוע בציאן (תכלת) או בלבן. עבור מסלול פשוט בעץ, יהי $c$ מספר הקודקודים בצבע ציאן ויהי $w$ מספר הקודקודים הלבנים במסלול. ערך המסלול הוא $(c + w) - 2 \times |c - w|$, כאשר $|c - w|$ הוא הערך המוחלט של $(c - w)$.
נגדיר את העומק של קודקוד $u$ כמספר הקשתות במסלול הקצר ביותר מקודקוד $1$ לקודקוד $u$. נגדיר את קודקוד המפתח של מסלול פשוט כקודקוד בעל העומק המינימלי מבין כל הקודקודים במסלול. ניתן להוכיח שקודקוד המפתח של מסלול פשוט הוא יחיד.
עבור כל $1 \le i \le n$, חשבו את הערך המקסימלי מבין כל המסלולים הפשוטים שקודקוד המפתח שלהם הוא $i$.
נזכיר כי מסלול בעץ הוא סדרה לא ריקה של קודקודים $p_1, p_2, \dots, p_k$ כך שכל זוג קודקודים סמוכים בסדרה זו מחובר באמצעות קשת. מסלול פשוט הוא מסלול שבו כל הקודקודים שונים זה מזה. גם קודקוד בודד יכול להוות מסלול פשוט.
קלט
ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^5$) המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:
השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 4 \times 10^5$) המציין את מספר הקודקודים.
השורה השנייה מכילה מחרוזת 01 באורך $n$, המציינת את הצבע של כל קודקוד. אם התו ה-$i$ הוא 0, הקודקוד ה-$i$ צבוע בציאן; אחרת, הקודקוד ה-$i$ צבוע בלבן.
ב-$(n - 1)$ השורות הבאות, השורה ה-$i$ מכילה שני מספרים שלמים $u_i$ ו-$v_i$ ($1 \le u_i, v_i \le n$), המציינים קשת המחברת בין הקודקודים $u_i$ ו-$v_i$. מובטח שהקשתות הנתונות יוצרות עץ.
מובטח שסכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $4 \times 10^5$.
פלט
עבור כל מקרה בדיקה הדפיסו $n$ שורות, שכל אחת מהן מכילה מספר שלם אחד. השורה ה-$i$ היא הערך המקסימלי מבין כל המסלולים הפשוטים שקודקוד המפתח שלהם הוא $i$.
דוגמאות
הערה
3
8
00101110
1 2
1 3
3 4
3 5
5 6
5 7
7 8
2
01
1 2
2
00
1 2
6
-1
3
-1
1
-1
2
-1
2
-1
-1
-1