Nie chodzi o pieniądze, chodzi o przekazanie wiadomości.
W sieci $n$ osób połączonych w strukturę drzewa osoba $1$ chce wysłać wiadomość do osoby $n$. Istnieje $10^9$ różnych języków ponumerowanych od $1$ do $10^9$. Osoba $i$ zna wszystkie języki z przedziału $[l_i, r_i]$.
Osoba $1$ zaczyna z kartką papieru i może zapisać początkową wiadomość w dowolnym języku, którym się posługuje. W każdej turze osoba trzymająca aktualnie kartkę może wykonać jedną z następujących czynności:
- Przekazać kartkę sąsiedniej osobie w drzewie.
- Jeśli rozumie język, w którym aktualnie napisana jest wiadomość na kartce, przetłumaczyć ją na dowolny inny znany sobie język (nadpisując oryginał).
Znajdź minimalną liczbę tur potrzebnych do tego, aby osoba $n$ otrzymała kartkę z wiadomością napisaną w języku, który rozumie.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $n$ — liczbę osób.
Kolejne $n - 1$ wierszy zawiera po dwie liczby całkowite $u$ oraz $v$, opisujące krawędź pomiędzy osobami $u$ i $v$ w drzewie.
Kolejne $n$ wierszy zawiera po dwie liczby całkowite $l_i$ oraz $r_i$ — przedział opisujący języki, którymi posługuje się osoba $i$.
Wyjście
Wypisz jedną liczbę całkowitą — minimalną liczbę tur potrzebnych, aby osoba $n$ otrzymała wiadomość w języku, który rozumie.
Ograniczenia
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ dla wszystkich krawędzi,
- $u \neq v$ dla wszystkich krawędzi,
- $1 \le l_i \le r_i \le 10^9$,
- jest zagwarantowane, że każda osoba może wysłać wiadomość do każdej innej osoby (być może wymagając serii tłumaczeń).
Przykład 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Uwagi
W przykładzie drzewo jest ścieżką.
Osoba $1$ zna języki $1, 2, 3$. Osoba $2$ zna języki $2, 3, 4$. Osoba $3$ zna języki $3, 4, 5$. Osoba $4$ zna języki $4, 5, 6$.
Jedno z optymalnych rozwiązań wygląda następująco. Najpierw osoba $1$ zapisuje wiadomość w języku $3$. Następnie kolejne osoby wykonują tury:
- Osoba $1$ przekazuje kartkę osobie $2$.
- Osoba $2$ tłumaczy wiadomość z języka $3$ na język $4$.
- Osoba $2$ przekazuje kartkę osobie $3$.
- Osoba $3$ przekazuje kartkę osobie $4$.
Osoba $4$ ma teraz wiadomość w języku $4$, który rozumie. Minimalna liczba potrzebnych tur wynosi cztery.