الأمر لا يتعلق بالمال، بل بإيصال رسالة.
في شبكة مكونة من $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$، وهي لغة يفهمها. الحد الأدنى لعدد الأدوار اللازمة هو أربعة.