Zagrade

Μια έκφραση είναι μια συμβολοσειρά που αποτελείται μόνο από σωστά ζευγαρωμένες παρενθέσεις. Για παράδειγμα, "~()()~" και "~(()())~" είναι εκφράσεις, ενώ τα "~)(~" και "~()(~" δεν είναι. Μπορούμε να ορίσουμε τις εκφράσεις επαγωγικά ως εξής:

• Το "~()~" είναι μια έκφραση.
  
• Αν το ~a~ είναι έκφραση, τότε το "~(a)~" είναι επίσης έκφραση.
  
• Αν το ~a~ και το ~b~ είναι εκφράσεις, τότε το "~ab~" είναι επίσης έκφραση.
  

Ένα δέντρο είναι μια δομή που αποτελείται από ~n~ κόμβους που συμβολίζονται με αριθμούς από το ~1~ έως το ~n~ και ~n - 1~ ακμές είναι τοποθετημένες έτσι ώστε να υπάρχει μια μοναδική διαδρομή μεταξύ κάθε δύο κόμβων. Επιπλέον, ένας χαρακτήρας γράφεται σε κάθε κόμβο. Ο χαρακτήρας είναι είτε ανοιχτή παρένθεση "(" είτε κλειστή παρένθεση ")". Για διαφορετικούς κόμβους ~a~ και ~b~, το ~w_{a,b}~ είναι μια συμβολοσειρά που λαμβάνεται διασχίζοντας τη μοναδική διαδρομή από το ~a~ στο ~b~ και, ένα προς ένα, προσθέτοντας τον χαρακτήρα που γράφτηκε στον κόμβο που περνάμε. Η συμβολοσειρά ~w_{a,b}~ περιέχει επίσης τον χαρακτήρα που είναι γραμμένος στον κόμβο ~a~ (στην πρώτη θέση) και ο χαρακτήρας που είναι γραμμένος στον κόμβο ~b~ (στην τελευταία θέση).
Βρείτε τον συνολικό αριθμό των ζευγών διαφορετικών κόμβων ~a~ και ~b~ έτσι ώστε τo ~w_{a,b}~ να είναι σωστή έκφραση.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ - τον αριθμό των κόμβων στο δέντρο. Η ακόλουθη γραμμή περιέχει μια συμβολοσειρά ~n~ χαρακτήρων όπου κάθε χαρακτήρας είναι είτε ")" είτε "(", ο ~j~-ος χαρακτήρας στη συμβολοσειρά είναι ο χαρακτήρας γραμμένος στον κόμβο ~j~. Κάθε μία από τις ακόλουθες ~n - 1~ γραμμές περιέχει δύο διαφορετικούς θετικούς ακέραιους ~x~ και ~y (1 \le x,\,y \le n)~ - οι ετικέτες των κόμβων που συνδέονται άμεσα με μια ακμή.

Έξοδος

Εκτυπώστε τον απαιτούμενο αριθμό ζευγών.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~n\le 1\,000~
2	30	~n\le 300\,000~, το δέντρο είναι μια αλυσίδα- κάθε κόμβος ~x=1,\,\ldots,\,n-1~ είναι συνδεδεμένος με τον κόμβο ~x+1~
3	60	~n \le 300\,000~

Παραδείγματα

input

4
(())
1 2
2 3
3 4

output

2

input

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

output

3

input

7
)()()((
1 2
1 3
1 6
2 4
4 5
5 7

output

6