金の問題じゃない、メッセージを伝えることが重要なんだ。
木構造でつながった $n$ 人のネットワークにおいて、人 $1$ が人 $n$ にメッセージを送りたいと考えています。$1$ から $10^9$ までの番号が付けられた $10^9$ 種類の異なる言語があります。人 $i$ は区間 $[l_i, r_i]$ に含まれるすべての言語を話せます。
人 $1$ は最初に1枚の紙を持っており、自分が話せる任意の言語で最初のメッセージを書くことができます。各ターンにおいて、現在紙を持っている人は次のいずれか1つを行うことができます。
- 木において隣接する人に紙を渡す。
- 現在紙に書かれている言語を理解できる場合、それを自分が話せる他の任意の言語に翻訳する(元の文章を上書きする)。
人 $n$ が自分の理解できる言語で書かれたメッセージの載った紙を受け取るために必要な最小ターン数を求めてください。
入力
1行目には、人数を表す単一の整数 $n$ が与えられます。
続く $n - 1$ 行にはそれぞれ、木における人 $u$ と人 $v$ の間の辺を表す2つの整数 $u$ と $v$ が与えられます。
さらに続く $n$ 行にはそれぞれ、人 $i$ が話せる言語の区間を表す2つの整数 $l_i$ と $r_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つは以下の通りです。まず、人 $1$ が言語 $3$ でメッセージを書きます。その後、ターンを進めていきます。
- 人 $1$ が人 $2$ に紙を渡す。
- 人 $2$ がメッセージを言語 $3$ から言語 $4$ に翻訳する。
- 人 $2$ が人 $3$ に紙を渡す。
- 人 $3$ が人 $4$ に紙を渡す。
これで人 $4$ は自分が理解できる言語 $4$ で書かれたメッセージを受け取りました。必要な最小ターン数は 4 です。