ในวิทยาการคอมพิวเตอร์ ปัญหาเอ็นพีบริบูรณ์ (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$

หมายเหตุ: ดีกรีของโหนดหนึ่งๆ ในต้นไม้หมายถึงจำนวนเส้นเชื่อมที่เชื่อมต่อกับโหนดนั้นโดยตรง