Задано корневое дерево, состоящее из n вершин. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n. Корнем дерева является вершина с номером 1.
Каждая вершина дерева имеет определенный цвет, цвет вершины v будем обозначать cv, изначально cv = 0.
В задаче вам требуется раскрасить дерево в заданные цвета с помощью минимального числа действий. За одно действие вы можете выбрать вершину v и цвет x, и покрасить все вершины поддерева v (включая v) в цвет x, то есть для всех вершин u таких, что путь от корня до u содержит вершину v, сделать cu = x.
Гарантируется, что все вершины надо покрасить в цвет, отличный от 0.
Определение корневого дерева можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Дерево_(теория_графов).
Выходные данные
На первой и единственной строке выведите одно целое число — минимальное число действий, за которое можно покрасить дерево в желаемые цвета.
Примечание
Первый пример расположен на следующей картинке (числа обозначают номера вершин):
Первым действием мы красим все вершины поддерева вершины 1 в цвет 2 (числа обозначают цвета):
Вторым действием мы красим все вершины поддерева вершины 5 в цвет 1:
Третьим действием мы красим все вершины поддерева вершины 2 в цвет 1:
Второй пример расположен на следующей картинке (числа обозначают номера вершин):
Первым действием мы красим все вершины поддерева вершины 1 в цвет 3 (числа обозначают цвета):
Вторым действием мы красим все вершины поддерева вершины 3 в цвет 1:
Третьим действием мы красим все вершины поддерева вершины 6 в цвет 2:
Четвертым действием мы красим все вершины поддерева вершины 4 в цвет 1:
Пятым действием мы красим все вершины поддерева вершины 7 в цвет 3:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 2 1 5
2 1 1 1 1 1
|
3
|
|
2
|
7
1 1 2 3 1 4
3 3 1 1 1 2 3
|
5
|