Det handlar inte om pengarna, det handlar om att skicka ett meddelande.
I ett nätverk av $n$ personer sammankopplade i en trädstruktur vill person $1$ skicka ett meddelande till person $n$. Det finns $10^9$ olika språk numrerade från $1$ till $10^9$. Person $i$ talar alla språk i intervallet $[l_i, r_i]$.
Person $1$ börjar med ett pappersark och kan skriva det ursprungliga meddelandet på vilket språk som helst som hen talar. I varje drag kan den person som för tillfället håller i pappret göra något av följande:
- Skicka pappret vidare till en grannperson i trädet.
- Om hen förstår språket som för närvarande står skrivet på pappret, översätta det till något annat språk som hen talar (och skriva över originalet).
Hitta det minsta antalet drag som krävs för att person $n$ ska få pappret med ett meddelande skrivet på ett språk som hen förstår.
Indata
Den första raden innehåller ett enda heltal $n$ — antalet personer.
De följande $n - 1$ raderna innehåller var och en två heltal $u$ och $v$, som beskriver en kant mellan personerna $u$ och $v$ i trädet.
De följande $n$ raderna innehåller var och en två heltal $l_i$ och $r_i$ — intervallet som beskriver de språk som person $i$ talar.
Utdata
Skriv ut ett enda heltal — det minsta antalet drag som behövs för att person $n$ ska få meddelandet på ett språk som hen förstår.
Begränsningar
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ för alla kanter,
- $u \neq v$ för alla kanter,
- $1 \le l_i \le r_i \le 10^9$,
- det garanteras att vilken person som helst kan skicka ett meddelande till vilken annan person som helst (eventuellt via en serie översättningar).
Exempel 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Anmärkningar
I exemplet är trädet en väg.
Person $1$ talar språken $1, 2, 3$. Person $2$ talar språken $2, 3, 4$. Person $3$ talar språken $3, 4, 5$. Person $4$ talar språken $4, 5, 6$.
En optimal lösning är följande. Först skriver person $1$ meddelandet på språk $3$. Sedan börjar personerna göra sina drag:
- Person $1$ skickar pappret till person $2$.
- Person $2$ översätter meddelandet från språk $3$ till språk $4$.
- Person $2$ skickar pappret till person $3$.
- Person $3$ skickar pappret till person $4$.
Person $4$ har nu meddelandet på språk $4$, vilket hen förstår. Det minsta antalet drag som behövs är fyra.