\problemname{Balanced Tree Path}

You are given a tree where each node is annotated with a character from {\tt ()[]\{\}}.
A path is a sequence of one or more nodes where no node is repeated and every pair of adjacent 
nodes is connected with an edge.
A path is balanced if the characters at each node, when concatenated, form a balanced string.
A string is balanced if it satisfies the following definition:
\begin{itemize}
\item An empty string is balanced.
\item If $s$ is a balanced string, then {\tt (}$s${\tt )}, {\tt [}$s${\tt ]}, and  {\tt \{}$s${\tt \}} are balanced strings.
\item if $a$ and $b$ are balanced strings, then $ab$ ($a$ concatenated with $b$) is a balanced string.
\end{itemize}

Compute the number of balanced paths over the entire tree.

\section*{Input}

The first line of input contains a single integer $n$ ($2 \le n \le 5 \cdot 10^3$).

The next line contains a string of $n$ characters, where each character is one of {\tt ()[]\{\}}.

Each of the next $n-1$ lines contains two integers, $u$ and $v$ ($1 \le u < v \le n$), indicating
that nodes $u$ and $v$ are connected with an edge. It is guaranteed the graph is a tree.

\section*{Output}

Output a single integer, which is the number of balanced paths over the entire tree.