Дело не в деньгах, дело в том, чтобы отправить послание.
В сети из $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$, который он понимает. Минимальное необходимое количество ходов равно четырём.