给定一棵包含 $n$ 个节点的无向树。节点编号为 $1$ 到 $n$。每个节点都被标记为 '(' 或 ')'。令 $l[u \to v]$ 表示连接从 $u$ 到 $v$ 的简单路径上所有节点的标签所构成的字符串。（注意：树中任意两点间的简单路径是唯一的。）

平衡字符串定义如下： 空字符串是平衡的。 对于任意平衡字符串 $s$，字符串 "(" $s$ ")" 是平衡的。 对于任意平衡字符串 $s$ 和 $t$，字符串 $st$（$s$ 与 $t$ 的拼接）是平衡的。 其他任何字符串均不平衡。

计算满足 $l[u \to v]$ 为平衡字符串的有序节点对 $(u, v)$ 的数量。

输入格式

输入包含单个测试用例。输入的第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树的节点数。下一行包含一个长度为 $n$ 的字符串，其中每个字符均为 '(' 或 ')'。字符串的第 $x$ 个字符表示树中节点 $x$ 的标签。接下来的 $n - 1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示节点 $a_i$ 和 $b_i$ 之间有一条边。保证给定的图是一棵树。

输出格式

输出一行，包含满足 $l[u \to v]$ 为平衡字符串的有序节点对 $(u, v)$ 的数量。

样例

样例输入 1

2
()
1 2

样例输出 1

1

样例输入 2

4
(())
1 2
2 3
3 4

样例输出 2

2

样例输入 3

5
()())
1 2
2 3
2 4
1 5

样例输出 3

4