تُعطى شجرة تحتوي على $n$ رأسًا، وكل رأس ملون إما باللون السماوي (cyan) أو الأبيض. بالنسبة لأي مسار بسيط في الشجرة، ليكن $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