Справа не в грошах, а в тому, щоб донести повідомлення.
У мережі з людей, з’єднаних у дерево, людина хоче передати повідомлення людині . Існує 10^9 різних мов, пронумерованих від до 10^9. Людина володіє всіма мовами з проміжку [l_i, r_i].
Людина починає з аркушем паперу та може записати початкове повідомлення будь-якою мовою, якою вона володіє. За один хід людина, яка зараз тримає аркуш, може виконати одну з таких дій.
Передати аркуш сусідній людині в дереві.
Якщо вона розуміє мову, якою наразі написано повідомлення, перекласти його на будь-яку іншу мову, якою вона володіє (замінюючи початковий текст).
Знайдіть мінімальну кількість ходів, необхідну для того, щоб людина отримала аркуш із повідомленням, написаним мовою, яку вона розуміє.
У першому рядку задано ціле число — кількість людей.
У наступних n-1 рядках задано по два цілі числа та , що описують ребро між людьми та у дереві.
У наступних рядках задано по два цілі числа l_i та r_i — проміжок мов, якими володіє людина .
2 \le n \le 2 \cdot 10^5,
1 \le u, v \le n для всіх ребер,
u \ne v для всіх ребер,
1 \le l_i \le r_i \le 10^9,
гарантовано, що будь-яка людина може передати повідомлення будь-якій іншій (можливо, через послідовність перекладів).
Виведіть одне ціле число — мінімальну кількість ходів, необхідну для того, щоб людина отримала повідомлення мовою, яку вона розуміє.
Приклад
У прикладі дерево є простим шляхом.
Людина володіє мовами , , . Людина володіє мовами , , . Людина володіє мовами , , . Людина володіє мовами , , .
Один з оптимальних способів передати повідомлення такий. Спочатку людина записує повідомлення мовою . Потім виконуються такі ходи.
Людина передає аркуш людині .
Людина перекладає повідомлення з мови мовою .
Людина передає аркуш людині .
Людина передає аркуш людині .
Тепер людина отримала повідомлення мовою , яку вона розуміє. Мінімальна кількість необхідних ходів дорівнює чотирьом.