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