Чтобы попасть в заброшенный дом, в котором прячется Оно, ребятам нужно открыть дверь с хитроумным замком. Этот замок представляет собой дерево из $$$n$$$ вершин, каждая из которых покрашена в белый или черный цвет. Чтобы открыть замок, нужно уничтожить все вершины этого дерева. Для этого ребята могут выполнять две операции:
Разумеется, ребятам хочется поскорее попасть в дом, поэтому им интересно узнать, какое минимальное количество операций им потребуется, чтобы открыть замок.
В первый строке дано целое число $$$n$$$ — количество вершин в графе ($$$1 \le n \le 200\,000$$$). В следующей строке дана строка $$$s$$$ длины $$$n$$$ из символов $$$0$$$ и $$$1$$$. Если $$$i$$$-й символ строки $$$s$$$ равен $$$0$$$, то $$$i$$$-я вершина покрашена в белый цвет, иначе — в черный. В следующих $$$n - 1$$$ строках дано по два целых числа $$$a_i$$$ и $$$b_i$$$ — ребра дерева ($$$1 \le a_i, b_i \le n$$$).
Гарантируется, что ребра образуют дерево.
Выведите одно число — минимальное количество операций, необходимое, чтобы открыть замок.
4 1000 1 2 1 3 1 4
2
В первом тесте замок можно открыть за два действия следующим образом: