当前没有测试数据。

题目描述

智乃有一颗由 $n$ 个节点组成的无根树。每个节点颜色为白色或黑色。定义黑白树的权值为所有起点为黑色、终点为白色的简单路径长度之和（路径长度指边的数目）。现在需要计算切断第 $i$ 条边后，产生的两棵黑白树的权值。所有询问互相独立，不会真正切除树上的边。简单路径指经过的顶点和边互不相同的路径。

输入描述

第一行输入一个正整数 $n\left(2\leq n \leq 10^5\right)$ 代表树上节点的数量。
第二行输入一个长度为 $n$、仅由字符 $\texttt{`w'}$ 和 $\texttt{`b'}$ 组成的字符串 $s_1s_2\cdots s_n$ 代表每个节点的颜色。其中 $s_i = \texttt{`w'}$ 表示节点 $i$ 是白色，$s_i = \texttt{`b'}$ 表示节点 $i$ 是黑色。
此后 $n-1$ 行，第 $i$ 行输入两个正整数 $u_i,v_i\left(1\leq u_i,v_i \leq n;\ u_i \neq v_i\right)$ 代表树上第 $i$ 条边连接的两个节点。

输出描述

共 $n-1$ 行，第 $i$ 行输出两个整数，代表去掉第 $i$ 条边后，新产生两棵树的权值。假设这条边连接 $u_i$ 和 $v_i$，则第一个整数表示 $u_i$ 所在树的权值，第二个整数表示 $v_i$ 所在树的权值。

样例1

输入

5
bwbwb
1 2
2 5
4 1
3 1

输出

3 1
6 0
0 4
0 6