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

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

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

Формат входных данных

В первый строке дано целое число n - количество вершин в графе (1 ⩽ n ⩽ 200 000). В следующей строке дана строка s длины n из символов 0 и 1. Если i-й символ строки s равен 0, то i-я вершина покрашена в белый цвет, иначе - в черный. В следующих n−1 строках дано по два целых числа a_i и b_i - ребра дерева (1 ⩽ a_i, b_i ⩽ n).

Гарантируется, что ребра образуют дерево.

Формат выходных данных

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

Пример

Примечание

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

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