Мовний бар'єр

Обмеження: 5 сек., 512 МіБ

Справа не в грошах, а в тому, щоб донести повідомлення.

У мережі з \(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 \ne v\) для всіх ребер,

\(1 \le l_i \le r_i \le 10^9\),

гарантовано, що будь-яка людина може передати повідомлення будь-якій іншій (можливо, через послідовність перекладів).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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. Людина \(1\) передає аркуш людині \(2\).

2. Людина \(2\) перекладає повідомлення з мови \(3\) мовою \(4\).

3. Людина \(2\) передає аркуш людині \(3\).

4. Людина \(3\) передає аркуш людині \(4\).

Тепер людина \(4\) отримала повідомлення мовою \(4\), яку вона розуміє. Мінімальна кількість необхідних ходів дорівнює чотирьом.