Ви граєте у свою улюблену мобільну гру. Карта гри складається з ~N~ (~2≤N≤10^5~) кімнат, помічених ~1…N~ з'єднаних ~N-1~ ребрами так, що утворюють дерево.

Ви можете дослідити карту, виконуючи серію "подорожей". Подорож це простий шлях з кімнати 1 до будь-якої іншої кімнати на дереві. Коли ви закінчуєте одну подорож, ви можете почати іншу знову з кімнати 1 . Карта завершена, коли кожна кімната відвідана хоча б однією подорожжю. Ваша головна мета – завершити карту мінімальною кількістю подорожей.

Ваша друга мета – зібрати якнайбільше зілля. Перш ніж розпочнуться подорожі, зілля з'явиться у деякій кімнаті. Ви можете взяти зілля, відвідавши кімнату, де з'явилося зілля перед поточною подорожжю. Якщо Ви не візьмете зілля, воно зникне, коли ця подорож закінчиться, і Ви не зможете взяти її у майбутній подорожі.

Як розумний програміст, після перегляду файлів гри, Ви змогли передбачити, де з'явиться зілля перед наступними ~N~ подорожами.

Яка максимальна кількість зілля, яку Ви можете зібрати за мінімальної кількості подорожей?

Формат вхідних даних

Перший рядок введення містить ціле число ~N~, кількість кімнат на карті.

Потім слідують ~N~ розділених одиночними пробілами цілих чисел ~p_1,p_2,…,p_N~ , ~1≤p_i≤N~ , де ~p_i~ це кімната, в якій з'явиться зілля перед ~i~-ю подорожжю.

Далі йдуть ~N-1~ рядків, що містять два розділених пробілами цілих числа ~a,b~ (~1≤a,b≤N~) - ребро між вершинами ~a~ і ~b~ . Гарантується, що ці ребра утворюють дерево.

Формат вихідних даних

Виведіть один рядок, що містить максимальну кількість зілля, яку Ви можете зібрати за мінімальну кількість подорожей.

ОЦІНЮВАННЯ:

• Тести 2 -7 (30 балів): ~N≤1000~
• Тести 8-15 (70 балів): Немає додаткових обмежень.

Приклад вхідних даних

5
5 4 3 2 1
1 2
1 3
3 4
3 5

Приклад вихідних даних

2

У цьому випадку мінімальна кількість необхідних подорожей дорівнює 3 .

Один оптимальний план, який збирає два зілля за три подорожі такий:

• Подорож 1: 1→3→5 (Беремо зілля у 5)
• Подорож 2: 1→3→4 (Беремо зілля у 4)
• Подорож 3: 1→2 (завершуємо подорож і ігноруємо зілля в 3)

Альтернативний план:

• Подорож 1: 1→2 (немає зілля)
• Подорож 2: 1→3→4 (Беремо зілля в 4)
• Подорож 3: 1→3→5 (Беремо зілля 3)