Вы играете в свою любимую мобильную игру. Карта игры состоит из
\(N\) \((2 \leq N \leq 10^5)\) комнат, помеченных \(1\dots N\) соединённых
\(N-1\) ребрами так, что формируют дерево.
Вы можете исследовать карту, выполняя серию "путешествий". Путешествие
это простой путь из комнаты \(1\) в любую другую комнату на дереве.
Когда Вы заканчиваете одно путешествие, Вы можете начать другое снова из комнаты
\(1\). Карта завершена, когда каждая из комнат посещена хотя бы одним путешествием.
Ваша главная цель - завершить карту минимальным количеством путешествий.
Ваша вторая цель - собрать как можно больше зелий.
Прежде чем начнутся путешествия, зелье появится в некоторой комнате.
Вы можете взять зелье, посетив комнату, в которой появилось зелье перед текущим
путешествием. Если Вы не возьмёте зелье, оно исчезнет, когда это путешествие
закончится, и Вы не сможете взять его в будущем путешествии.
Как умный программист, после просмотра файлов игры, Вы можете
предсказать где появится зелье перед следующими \(N\) путешествиями.
Каково максимальное количество зелий, которое Вы можете собрать
при минимальном количестве путешествий?
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит целое число
\(N\), количество комнат на карте.
Затем следуют \(N\) разделённых одиночными пробелами целых чисел
\(p_1 \: p_2 \: \ldots \: p_N\), \(1 \leq p_i \leq N\),
где \(p_i\) эта комната, в которой появится зелье перед i-ым путешествием.
Далее идут \(N-1\) строк, содержащих по два разделённых одиночными пробелами
целых числа \(a \: b\) \((1 \leq a, b \leq N)\) представляющих ребро между
вершинами \(a\) и \(b\). Гарантируется, что эти ребра образуют дерево.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одну строку, содержащую максимальное количество зелий,
которое Вы можете собрать за минимальное количество путешествий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 4 3 2 1
1 2
1 3
3 4
3 5
|
2
|