You are given an undirected tree with $n$ nodes. The nodes are numbered 1 through $n$. Each node is labeled with either '(' or ')'. Let $l[u \rightarrow v]$ denote the string obtained by concatenating the labels of the nodes on the simple path from $u$ to $v$. (Note that the simple path between two nodes is uniquely determined on a tree.) A balanced string is defined as follows:
Calculate the number of the ordered pairs of the nodes ($u$, $v$) such that $l[u \rightarrow v]$ is balanced.
The input consists of a single test case. The input starts with an integer $n (2 \leq n \leq 10^5)$, which is the number of nodes of the tree. The next line contains a string of length $n$, each character of which is either '(' or ')'. The $x$-th character of the string represents the label of the node $x$ of the tree. Each of the following $n - 1$ lines contains two integers $a_i$ and $b_i$ $(1 \leq a_i, b_i \leq n)$, which represents that the node $a_i$ and the node $b_i$ are connected by an edge. The given graph is guaranteed to be a tree.
Display a line containing the number of the ordered pairs ($u$, $v$) such that $l[u \rightarrow v]$ is balanced.
2 () 1 2
4 (()) 1 2 2 3 3 4
5 ()()) 1 2 2 3 2 4 1 5