Ce n'est pas une question d'argent, c'est une question de faire passer un message.
Dans un réseau de $n$ personnes reliées par une structure d'arbre, la personne $1$ veut envoyer un message à la personne $n$. Il existe $10^9$ langues différentes numérotées de $1$ à $10^9$. La personne $i$ parle toutes les langues de l'intervalle $[l_i, r_i]$.
La personne $1$ commence avec une feuille de papier et peut écrire le message initial dans n'importe quelle langue qu'elle parle. À chaque tour, la personne qui tient actuellement la feuille peut effectuer l'une des actions suivantes :
- Passer la feuille à une personne voisine dans l'arbre.
- Si elle comprend la langue actuellement écrite sur la feuille, la traduire dans n'importe quelle autre langue qu'elle parle (en écrasant l'original).
Trouvez le nombre minimal de tours pour que la personne $n$ reçoive la feuille avec un message écrit dans une langue qu'elle comprend.
Entrée
La première ligne contient un seul entier $n$ — le nombre de personnes.
Les $n - 1$ lignes suivantes contiennent chacune deux entiers $u$ et $v$, décrivant une arête entre les personnes $u$ et $v$ dans l'arbre.
Les $n$ lignes suivantes contiennent chacune deux entiers $l_i$ et $r_i$ — l'intervalle décrivant les langues parlées par la personne $i$.
Sortie
Affichez un seul entier — le nombre minimal de tours nécessaires pour que la personne $n$ reçoive le message dans une langue qu'elle comprend.
Contraintes
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ pour toutes les arêtes,
- $u \neq v$ pour toutes les arêtes,
- $1 \le l_i \le r_i \le 10^9$,
- il est garanti que n'importe quelle personne peut envoyer un message à n'importe quelle autre personne (en ayant éventuellement recours à une série de traductions).
Exemple 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Notes
Dans l'exemple, l'arbre est un chemin.
La personne $1$ parle les langues $1, 2, 3$. La personne $2$ parle les langues $2, 3, 4$. La personne $3$ parle les langues $3, 4, 5$. La personne $4$ parle les langues $4, 5, 6$.
Une solution optimale est la suivante. Tout d'abord, la personne $1$ écrit le message dans la langue $3$. Ensuite, les personnes commencent à jouer leurs tours :
- La personne $1$ passe la feuille à la personne $2$.
- La personne $2$ traduit le message de la langue $3$ vers la langue $4$.
- La personne $2$ passe la feuille à la personne $3$.
- La personne $3$ passe la feuille à la personne $4$.
La personne $4$ a maintenant le message dans la langue $4$, qu'elle comprend. Le nombre minimal de tours nécessaires est de quatre.