$n$개의 정점으로 이루어진 트리가 주어지며, 각 정점은 청록색(cyan) 또는 흰색(white)으로 칠해져 있습니다. 트리의 단순 경로에 대해, 경로에 포함된 청록색 정점의 개수를 $c$, 흰색 정점의 개수를 $w$라고 합시다. 이 경로의 가치는 $(c + w) - 2 \times |c - w|$이며, 여기서 $|c - w|$는 $(c - w)$의 절댓값입니다.
정점 $u$의 깊이를 정점 $1$에서 정점 $u$까지의 최단 경로에 있는 간선의 개수로 정의합니다. 단순 경로의 핵심 정점(key vertex)을 경로에 속한 모든 정점 중 깊이가 최소인 정점으로 정의합니다. 단순 경로의 핵심 정점은 유일함을 증명할 수 있습니다.
각 $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$)이 주어집니다.
두 번째 줄에는 각 정점의 색상을 나타내는 길이 $n$인 01-문자열이 주어집니다. $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