Svjetlo

Ωχ όχι! Είναι νύχτα και ο μικρός Fabijan φοβάται το σκοτάδι. Ακόμη χειρότερα, ο πολυέλαιος στο δωμάτιό του είναι χαλασμένος.

Ο πολυέλαιος αποτελείται από ~n~ λαμπτήρες που συνδέονται με ~n - 1~ καλώδια, έτσι ώστε κάθε καλώδιο να συνδέει δύο λαμπτήρες και όλοι οι λαμπτήρες να συνδέονται, είτε απευθείας είτε μέσω άλλων λαμπτήρων. Με άλλα λόγια, ο πολυέλαιος είναι ένα δέντρο.

Κάθε λαμπτήρας έχει ένα κουμπί που αλλάζει την κατάστασή του. Εάν ο λαμπτήρας είναι σβηστός, πατώντας το κουμπί ανάβει και αν είναι αναμμένος, σβήνει. Στην αρχή, ορισμένοι λαμπτήρες είναι αναμμένοι και άλλοι είναι σβηστοί (είναι πιθανό να είναι όλοι σβηστοί). Όλοι οι ~n~ λαμπτήρες πρέπει να είναι αναμμένοι για να σταματήσει ο Fabijan να φοβάται, αφού μόνο τότε θα υπάρχει αρκετό φως στο δωμάτιο.

Ο Fabijan θα επιλέξει κάποια σειρά λαμπτήρων, έτσι λαμπτήρες οι οποίοι βρίσκονται διαδοχικά στη σειρά να συνδέονται απευθείας με κάποιο καλώδιο. Οι λαμπτήρες μπορούν να επαναλαμβάνονται. Στη συνέχεια θα ενεργοποιήσει τους λαμπτήρες στη σειρά. Δεδομένου ότι στον Fabijan αρέσει πολύ να πατάει κουμπιά, είτε σε λαμπτήρες, είτε σε πλυντήρια ρούχων, είτε σε ανελκυστήρες, κάθε φορά που βρίσκει έναν λαμπτήρα θα πατάει το αντίστοιχο κουμπί μία φορά, αλλάζοντας την κατάστασή του.

Βοηθήστε τον Fabijan προσδιορίζοντας το μήκος της συντομότερης σειράς λαμπτήρων, έτσι ώστε στο τέλος να ανάβουν όλοι οι λαμπτήρες. Θα υπάρχει τουλάχιστον ένας λαμπτήρας που θα είναι σβηστός στην αρχή.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n~, τον αριθμό των λαμπτήρων. Οι λαμπτήρες επισημαίνονται με ακέραιους αριθμούς από το 1 έως το ~n~.

Η δεύτερη γραμμή περιέχει μια ακολουθία από n χαρακτήρες '0' και '1'. Αν ο χαρακτήρας ~i~ ισούται με '0', τότε στην αρχή ο λαμπτήρας ~i~ είναι σβηστός και αν είναι ίσος με '1', είναι αναμμένος.

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

Έξοδος

Τυπώστε το ελάχιστο δυνατό μήκος μιας ακολουθίας, έτσι ώστε όλοι οι λαμπτήρες στο τέλος να είναι αναμμένοι.

Μπορεί να αποδειχθεί ότι μια τέτοια ακολουθία υπάρχει πάντα.

Βαθμολογία

Σε όλα τα υποπροβλήματα ισχύει ότι ~2 \le n \le 500\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le n \le 100~
2	30	Κάθε λαμπτήρας συνδέεται απευθείας με δύο, το πολύ, άλλους λαμπτήρες.
3	30	Όλοι οι λαμπτήρες σβήνουν στην αρχή.
4	30	Κανένας επιπλέον περιορισμός.

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

input

3
010
1 2
2 3

output

4

Επεξήγηση του 1ου παραδείγματος:

Ο Fabijan μπορεί να επιλέξει την ακολουθία ~1,\;2,\;3,\;2~.

input

5
00000
1 2
2 3
2 4
3 5

output

7

input

5
00100
1 2
2 3
2 4
3 5

output

8