في علوم الحاسوب، تُعدّ المسائل الكاملة في NP (NP-Complete، وتُختصر بـ NPC) فئةً من المسائل الكلاسيكية التي تجمع بين العمق النظري وصعوبة الحل؛ إذ لم يُعثر حتى الآن على خوارزمية ذات زمن كثير حدود لحلّها، ولكن بمجرد التغلّب على أي مسألة منها، ستُحلّ جميع مسائل NP بسهولة.

لطالما حلم الصغير W، الشغوف بأبحاث الخوارزميات، بتحدي مسائل NPC. وقد علم أن «مسألة أكبر بيان جزئي مستحث مشترك» الشهيرة في نظرية البيانات هي بالفعل مسألة NPC كلاسيكية. وأمام فجوة التعقيد التي يصعب تجاوزها على البيانات العامة، قرر الصغير W التراجع خطوةً إلى الوراء والبدء من الأشجار التي تتميز ببنية أكثر أناقة، لدراسة مسألة البيانات الجزئية المتصلة المتشاكلة على الأشجار.

تحديداً، يُعطى شجرتان غير مجذّرتين $T_1$ و $T_2$ تحتوي كلٌّ منهما على $n$ عقدة، وتُرقّم عقد كلتا الشجرتين على الترتيب من $1 \sim n$. يرغب الصغير W في اختيار مجموعة جزئية غير خالية من العقد $V_1$ في $T_1$، واختيار مجموعة جزئية غير خالية من العقد $V_2$ في $T_2$، مع الاحتفاظ بجميع الأضلاع الأصلية في الشجرة الأصلية بين العقد داخل كل مجموعة، مما يستحث بيانين جزئيين $G_1$ و $G_2$ على الترتيب.

يشترط الصغير W أن يحقق البيانان الجزئيان المستحثان $G_1, G_2$ معاً ما يلي:

1. الترابط: كلٌّ من $G_1$ و $G_2$ بيان متصل (وعلى وجه الخصوص، يُعتبر البيان الذي يحتوي على عقدة $1$ فقط متصلاً أيضاً).
2. التشاكل: $G_1$ و $G_2$ متشاكلان. أي يوجد تقابل (تناظر أحادي) $f : V_1 \to V_2$ من $V_1$ إلى $V_2$ بحيث إنه لكل $u, v \in V_1$، ترتبط $u$ و $v$ بضلع في $G_1$ إذا وفقط إذا ارتبطت $f(u)$ و $f(v)$ بضلع في $G_2$. ملاحظة: لا يُشترط أن يكون للعقدتين المتناظرتين $u$ و $f(u)$ نفس الرقم.

الآن، يسلّم الصغير W هذه المسألة المبسطة إليك: يرجى حساب أكبر عدد ممكن من العقد التي يمكن أن يحتويها بيان جزئي متصل متشاكل يحقق المتطلبات المذكورة أعلاه (أي إيجاد القيمة العظمى لـ $|V_1|$)؟

الإدخال

تُقرأ البيانات من stdin.

يحتوي السطر الأول على عدد صحيح موجب $n$ يمثل عدد العقد في كل شجرة.

تحتوي الأسطر الـ $n - 1$ التالية في كل سطر منها على عددين صحيحين موجبين $u, v$ يمثلان ضلعاً غير موجه $(u, v)$ في الشجرة $T_1$.

تحتوي الأسطر الـ $n - 1$ التالية في كل سطر منها على عددين صحيحين موجبين $u, v$ يمثلان ضلعاً غير موجه $(u, v)$ في الشجرة $T_2$.

الإخراج

يُكتب الإخراج إلى stdout.

اطبع سطراً واحداً يحتوي على عدد صحيح موجب يمثل أكبر عدد من العقد في البيان الجزئي المتصل المتشاكل المختار.

أمثلة

الإدخال 1

4
1 2
2 3
3 4
1 2
1 3
1 4

الإخراج 1

3

ملاحظة

نختار مجموعة العقد $V_1 = \{1, 2, 3\}$ في $T_1$، ومجموعة العقد $V_2 = \{1, 2, 3\}$ في $T_2$. عند مقابلة العقد $1, 2, 3$ في $V_1$ على الترتيب بالعقد $2, 1, 3$ في $V_2$، يكون البيانان الجزئيان المستحثان كلاهما سلسلة تحتوي على $3$ عقد، مما يحقق الترابط والتشاكل.

بما أن $T_1$ نفسها عبارة عن سلسلة، فإن أي بيان جزئي متصل منها يجب أن يكون سلسلة أيضاً؛ في حين أن أطول سلسلة في البيان النجمي $T_2$ تحتوي على $3$ عقد فقط، ولذلك يستحيل اختيار بيان جزئي متصل متشاكل يتجاوز عدد عقده $3$.

المثال 2

انظر الملفيْن npc/npc2.in و npc/npc2.ans في دليل المتسابق.

يحقق هذا المثال قيود المهمة الفرعية $1$.

المثال 3

انظر الملفيْن npc/npc3.in و npc/npc3.ans في دليل المتسابق.

يحقق هذا المثال قيود المهمة الفرعية $4$.

المثال 4

انظر الملفيْن npc/npc4.in و npc/npc4.ans في دليل المتسابق.

يحقق هذا المثال قيود المهمة الفرعية $7$.

المهام الفرعية

لجميع البيانات، يُضمن أن $1 \le n \le 500$، وأن رقمي طرفي كل ضلع يقعان بين $1 \sim n$، وأن البيانين المعطيين هما شجرتان صحيحتان.

الدرجة الكاملة لهذه المسألة هي $150$ نقطة، ويُعتمد فيها نظام التقييم المجمّع للمهام الفرعية. لن تحصل على درجة مهمة فرعية إلا إذا اجتزت جميع نقاط الاختبار في تلك المهمة الفرعية. يوضح الجدول أدناه تفاصيل نطاق البيانات لكل مهمة فرعية.

الخاصية الخاصة A: درجة جميع العقد في كلتا الشجرتين لا تتجاوز $3$.

الخاصية الخاصة B: يوجد حل أمثل يقوم تطبيق التشاكل فيه بمقابلة العقدة $1$ في $T_1$ بالعقدة $1$ في $T_2$.

الخاصية الخاصة C: يُضمن أن الإجابة النهائية لا تقل عن $n - 1$.

ملاحظة: درجة عقدة في الشجرة تعني عدد الأضلاع المتصلة مباشرة بتلك العقدة.