Kyse ei ole rahasta, vaan viestin lähettämisestä.
Puurakenteella yhdistetyssä $n$ ihmisen verkostossa henkilö $1$ haluaa lähettää viestin henkilölle $n$. On olemassa $10^9$ eri kieltä, jotka on numeroitu $1$:stä $10^9$:ään. Henkilö $i$ puhuu kaikkia välillä $[l_i, r_i]$ olevia kieliä.
Henkilöllä $1$ on aluksi paperiarkki, ja hän voi kirjoittaa alkuperäisen viestin millä tahansa puhumallaan kielellä. Jokaisella vuorolla paperia sillä hetkellä pitävä henkilö voi tehdä yhden seuraavista:
- Antaa paperin naapurihenkilölle puussa.
- Jos hän ymmärtää paperille sillä hetkellä kirjoitettua kieltä, kääntää sen mille tahansa muulle puhumalleen kielelle (korvaten alkuperäisen tekstin).
Etsi pienin mahdollinen vuorojen lukumäärä, jolla henkilö $n$ saa paperin, jossa on viesti hänen ymmärtämällään kielellä.
Syöte
Ensimmäinen rivi sisältää yhden kokonaisluvun $n$ — ihmisten lukumäärän.
Seuraavat $n - 1$ riviä sisältävät kukin kaksi kokonaislukua $u$ ja $v$, jotka kuvaavat kaaren henkilöiden $u$ ja $v$ välillä puussa.
Seuraavat $n$ riviä sisältävät kukin kaksi kokonaislukua $l_i$ ja $r_i$ — välin, joka kuvaa henkilön $i$ puhumia kieliä.
Tuloste
Tulosta yksi kokonaisluku — pienin vuorojen lukumäärä, joka tarvitaan, jotta henkilö $n$ saa viestin ymmärtämällään kielellä.
Rajoitukset
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ kaikille kaarille,
- $u \neq v$ kaikille kaarille,
- $1 \le l_i \le r_i \le 10^9$,
- on taattu, että kuka tahansa henkilö voi lähettää viestin kenelle tahansa toiselle henkilölle (mahdollisesti käännösketjun avulla).
Esimerkki 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Huomautukset
Esimerkissä puu on polku.
Henkilö $1$ puhuu kieliä $1, 2, 3$. Henkilö $2$ puhuu kieliä $2, 3, 4$. Henkilö $3$ puhuu kieliä $3, 4, 5$. Henkilö $4$ puhuu kieliä $4, 5, 6$.
Eräs optimaalinen ratkaisu on seuraava. Ensin henkilö $1$ kirjoittaa viestin kielellä $3$. Sitten henkilöt alkavat tehdä vuoroja:
- Henkilö $1$ antaa paperin henkilölle $2$.
- Henkilö $2$ kääntää viestin kielestä $3$ kieleen $4$.
- Henkilö $2$ antaa paperin henkilölle $3$.
- Henkilö $3$ antaa paperin henkilölle $4$.
Henkilöllä $4$ on nyt viesti kielellä $4$, jota hän ymmärtää. Pienin tarvittava vuorojen lukumäärä on neljä.