Деревянный замок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы попасть в заброшенный дом, в котором прячется Оно, ребятам нужно открыть дверь с хитроумным замком. Этот замок представляет собой дерево из $$$n$$$ вершин, каждая из которых покрашена в белый или черный цвет. Чтобы открыть замок, нужно уничтожить все вершины этого дерева. Для этого ребята могут выполнять две операции:

  1. Перекрасить еще не уничтоженную вершину из белого в черный, или из черного в белый.
  2. Запустить цепную реакцию, уничтожающую группу связных вершин одного цвета. Формально, ребята могут выбрать любую еще не уничтоженную вершину цвета $$$c$$$, уничтожить ее и все вершины цвета $$$c$$$, достижимые из нее по еще не уничтоженным вершинам цвета $$$c$$$.

Разумеется, ребятам хочется поскорее попасть в дом, поэтому им интересно узнать, какое минимальное количество операций им потребуется, чтобы открыть замок.

Входные данные

В первый строке дано целое число $$$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

Примечание

В первом тесте замок можно открыть за два действия следующим образом:

  1. Перекрасить вершину $$$1$$$ в белый цвет.
  2. Запустить цепную реакцию из вершины $$$1$$$, она уничтожит все вершины.