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

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

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

У мережі з людей, з’єднаних у дерево, людина хоче передати повідомлення людині . Існує 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,

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

Вихідні дані

Виведіть одне ціле число — мінімальну кількість ходів, необхідну для того, щоб людина отримала повідомлення мовою, яку вона розуміє.

Приклади

Приклад

Loading
Loading

Примітка

У прикладі дерево є простим шляхом.

Людина володіє мовами , , . Людина володіє мовами , , . Людина володіє мовами , , . Людина володіє мовами , , .

Один з оптимальних способів передати повідомлення такий. Спочатку людина записує повідомлення мовою . Потім виконуються такі ходи.

  1. Людина передає аркуш людині .

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

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

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

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