Дано дерево з $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