No se trata del dinero, se trata de enviar un mensaje.
En una red de $n$ personas conectadas mediante una estructura de árbol, la persona $1$ quiere enviar un mensaje a la persona $n$. Hay $10^9$ idiomas diferentes numerados del $1$ al $10^9$. La persona $i$ habla todos los idiomas en el intervalo $[l_i, r_i]$.
La persona $1$ comienza con una hoja de papel y puede escribir el mensaje inicial en cualquier idioma que hable. En cada turno, la persona que tiene actualmente el papel puede hacer una de las siguientes acciones:
- Pasar el papel a una persona vecina en el árbol.
- Si entiende el idioma escrito actualmente en el papel, traducirlo a cualquier otro idioma que hable (sobrescribiendo el original).
Encuentra el número mínimo de turnos para que la persona $n$ reciba el papel con un mensaje escrito en un idioma que entienda.
Entrada
La primera línea contiene un solo entero $n$ — el número de personas.
Las siguientes $n - 1$ líneas contienen cada una dos enteros $u$ y $v$, que describen una arista entre las personas $u$ y $v$ en el árbol.
Las siguientes $n$ líneas contienen cada una dos enteros $l_i$ y $r_i$ — el intervalo que describe los idiomas que habla la persona $i$.
Salida
Imprime un solo entero — el número mínimo de turnos necesarios para que la persona $n$ reciba el mensaje en un idioma que entienda.
Restricciones
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ para todas las aristas,
- $u \neq v$ para todas las aristas,
- $1 \le l_i \le r_i \le 10^9$,
- se garantiza que cualquier persona puede enviar un mensaje a cualquier otra persona (posiblemente requiriendo una serie de traducciones).
Ejemplo 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Notas
En el ejemplo, el árbol es un camino.
La persona $1$ habla los idiomas $1, 2, 3$. La persona $2$ habla los idiomas $2, 3, 4$. La persona $3$ habla los idiomas $3, 4, 5$. La persona $4$ habla los idiomas $4, 5, 6$.
Una solución óptima es la siguiente. Primero, la persona $1$ escribe el mensaje en el idioma $3$. Luego las personas comienzan a realizar turnos:
- La persona $1$ pasa el papel a la persona $2$.
- La persona $2$ traduce el mensaje del idioma $3$ al idioma $4$.
- La persona $2$ pasa el papel a la persona $3$.
- La persona $3$ pasa el papel a la persona $4$.
La persona $4$ ahora tiene el mensaje en el idioma $4$, el cual entiende. El número mínimo de turnos necesarios es cuatro.