Non è una questione di soldi, l'importante è mandare un messaggio.
In una rete di $n$ persone collegate da una struttura ad albero, la persona $1$ vuole inviare un messaggio alla persona $n$. Ci sono $10^9$ lingue diverse numerate da $1$ a $10^9$. La persona $i$ parla tutte le lingue nell'intervallo $[l_i, r_i]$.
La persona $1$ inizia con un foglio di carta e può scrivere il messaggio iniziale in qualsiasi lingua parli. A ogni turno, la persona che tiene attualmente il foglio può fare una delle seguenti cose:
- Passare il foglio a una persona vicina nell'albero.
- Se capisce la lingua attualmente scritta sul foglio, tradurla in qualsiasi altra lingua che parla (sovrascrivendo l'originale).
Trova il numero minimo di turni affinché la persona $n$ riceva il foglio con un messaggio scritto in una lingua che capisce.
Input
La prima riga contiene un singolo intero $n$ — il numero di persone.
Le successive $n - 1$ righe contengono ciascuna due interi $u$ e $v$, che descrivono un arco tra le persone $u$ e $v$ nell'albero.
Le successive $n$ righe contengono ciascuna due interi $l_i$ e $r_i$ — l'intervallo che descrive le lingue parlate dalla persona $i$.
Output
Stampa un singolo intero — il numero minimo di turni necessari affinché la persona $n$ riceva il messaggio in una lingua che capisce.
Vincoli
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ per tutti gli archi,
- $u \neq v$ per tutti gli archi,
- $1 \le l_i \le r_i \le 10^9$,
- è garantito che qualsiasi persona possa inviare un messaggio a qualsiasi altra persona (eventualmente richiedendo una serie di traduzioni).
Esempio 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Note
Nell'esempio, l'albero è un cammino.
La persona $1$ parla le lingue $1, 2, 3$. La persona $2$ parla le lingue $2, 3, 4$. La persona $3$ parla le lingue $3, 4, 5$. La persona $4$ parla le lingue $4, 5, 6$.
Una soluzione ottimale è la seguente. Prima, la persona $1$ scrive il messaggio nella lingua $3$. Poi le persone iniziano a fare i turni:
- La persona $1$ passa il foglio alla persona $2$.
- La persona $2$ traduce il messaggio dalla lingua $3$ alla lingua $4$.
- La persona $2$ passa il foglio alla persona $3$.
- La persona $3$ passa il foglio alla persona $4$.
La persona $4$ ora ha il messaggio nella lingua $4$, che capisce. Il numero minimo di turni necessari è quattro.