Deepest Balanced Parentheses Path in a Tree

Farmer John’s farm is organized as a tree of N pastures (1 ≤ N ≤ 40,000), where each pasture is labeled with either ( or ). A unique path connects any two pastures. Some of these paths, when the labels are read in order, form balanced parentheses strings. The nesting depth of a balanced string is defined as the maximum excess number of ( symbols over ) symbols in any prefix. For example, the balanced string ()()() has a nesting depth of 1 whereas ((()))() has a nesting depth of 3 because the prefix counts are 1, 2, 3, 2, 1, 0, 1, 0 respectively.

Your task is to find, among all paths in the tree that form a balanced parentheses string, the one with the maximum nesting depth and output that nesting depth. If no balanced path exists, output 0.

Note: The path need not be the longest balanced string – you are only required to maximize the nesting depth.

inputFormat

The input begins with a line containing a single integer N (the number of nodes). The next line contains a string of N characters, each being either ( or ), representing the label of nodes 1 through N respectively. Each of the following N - 1 lines contains two integers u and v (1-indexed), indicating an undirected edge between nodes u and v in the tree.

You may assume that the tree is connected and has no cycles.

outputFormat

Output a single integer – the maximum nesting depth among all balanced paths in the tree. If no balanced path exists, output 0.

sample

3
(()
1 2
2 3

1