זה לא עניין של כסף, זה עניין של העברת מסר.
ברשת של $n$ אנשים המחוברים במבנה של עץ, אדם $1$ רוצה לשלוח הודעה לאדם $n$. ישנן $10^9$ שפות שונות הממוספרות מ-$1$ עד $10^9$. אדם $i$ דובר את כל השפות בקטע $[l_i, r_i]$.
אדם $1$ מתחיל עם פיסת נייר ויכול לכתוב את ההודעה ההתחלתית בכל שפה שהוא דובר. בכל תור, האדם שמחזיק כעת בנייר יכול לעשות אחת מהפעולות הבאות:
- להעביר את הנייר לאדם שכן בעץ.
- אם הוא מבין את השפה שכתובה כעת על הנייר, לתרגם אותה לכל שפה אחרת שהוא דובר (תוך דריסת המקור).
מצאו את המספר המינימלי של תורות הדרוש כדי שאדם $n$ יקבל את הנייר עם הודעה הכתובה בשפה שהוא מבין.
קלט
השורה הראשונה מכילה מספר שלם יחיד $n$ — מספר האנשים.
$n - 1$ השורות הבאות מכילות כל אחת שני מספרים שלמים $u$ ו-$v$, המתארים קשת בין האנשים $u$ ו-$v$ בעץ.
$n$ השורות הבאות מכילות כל אחת שני מספרים שלמים $l_i$ ו-$r_i$ — הקטע המתאר את השפות שאדם $i$ דובר.
פלט
הדפיסו מספר שלם יחיד — המספר המינימלי של תורות הדרוש כדי שאדם $n$ יקבל את ההודעה בשפה שהוא מבין.
מגבלות
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ לכל הקשתות,
- $u \neq v$ לכל הקשתות,
- $1 \le l_i \le r_i \le 10^9$,
- מובטח שכל אדם יכול לשלוח הודעה לכל אדם אחר (ייתכן שבאמצעות סדרה של תרגומים).
דוגמה 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
הערות
בדוגמה, העץ הוא מסלול.
אדם $1$ דובר את השפות $1, 2, 3$. אדם $2$ דובר את השפות $2, 3, 4$. אדם $3$ דובר את השפות $3, 4, 5$. אדם $4$ דובר את השפות $4, 5, 6$.
פתרון אופטימלי אחד הוא כדלקמן. תחילה, אדם $1$ כותב את ההודעה בשפה $3$. לאחר מכן האנשים מתחילים לבצע תורות:
- אדם $1$ מעביר את הנייר לאדם $2$.
- אדם $2$ מתרגם את ההודעה משפה $3$ לשפה $4$.
- אדם $2$ מעביר את הנייר לאדם $3$.
- אדם $3$ מעביר את הנייר לאדם $4$.
לאדם $4$ יש כעת את ההודעה בשפה $4$, שאותה הוא מבין. המספר המינימלי של תורות הנדרש הוא ארבעה.