พิกกี้ (ผู้ซึ่งใช้เวลาว่างบริหารคณะกรรมการโปรโตคอลการเชื่อมต่อระหว่างดวงดาว) กำลังเผชิญกับปัญหาฮาร์ดแวร์ที่ละเอียดอ่อน โครงข่ายการสื่อสารล่าสุดซึ่งประกอบด้วยสถานีทวนสัญญาณ $n$ สถานีที่เชื่อมต่อกันด้วยสายไฟเบอร์ออปติก $(n - 1)$ เส้นเป็นโครงสร้างต้นไม้ พร้อมสำหรับการติดตั้งใช้งานแล้วในที่สุด อย่างไรก็ตาม ระบบจะต้องถูกเปิดใช้งานด้วยความระมัดระวังอย่างยิ่ง
กระบวนการเปิดใช้งานเกี่ยวข้องกับการยิงพัลส์เลเซอร์ไปตามเส้นทางที่กำหนด เส้นทางถูกนิยามว่าเป็นเส้นทางเชิงเดียวที่ไม่ซ้ำกันระหว่างสองสถานี เนื่องจากความเสี่ยงร้ายแรงของ "การแทรกสอดไหลย้อนกลับเชิงควอนตัม" ซึ่งเป็นปรากฏการณ์ที่ทำให้ทีมทนายความของคณะกรรมการนอนไม่หลับในยามค่ำคืน จึงต้องปฏิบัติตามโปรโตคอลต่อไปนี้อย่างเคร่งครัด:
- ต้องสร้างเส้นทางการส่งสัญญาณทีละเส้นทาง
- เพื่อป้องกันไฟกระชาก เส้นทางที่สร้างขึ้นใหม่แต่ละเส้นทางสามารถใช้สถานีร่วมกับเซตของสถานีที่ถูกเปิดใช้งานไปแล้วโดยเส้นทางก่อนหน้าได้ อย่างมากหนึ่งสถานี
กล่าวอย่างเป็นทางการ ให้ $S$ เป็นเซตของสถานีที่ถูกเปิดใช้งานอยู่ในปัจจุบัน สำหรับเส้นทางใหม่ $P$ ใดๆ ที่ประกอบด้วยเซตของสถานี $V(P)$ เงื่อนไข $|V(P) \cap S| \le 1$ จะต้องเป็นจริง เมื่อยิงพัลส์ตามเส้นทางสำเร็จแล้ว สถานีทั้งหมดตามเส้นทางนั้นจะถือเป็นส่วนหนึ่งของเซตที่เปิดใช้งานแล้ว $S$
ภารกิจของคุณ หากคุณเลือกที่จะรับมัน คือการหาจำนวนพัลส์เลเซอร์น้อยที่สุดที่ต้องใช้เพื่อเปิดใช้งานทุกสถานีในโครงข่ายทั้งหมด และระบุลำดับของเส้นทางดังกล่าวหนึ่งลำดับเพื่อสร้างความพึงพอใจให้กับฝ่ายกฎหมาย

ภาพประกอบของชุดข้อมูลทดสอบตัวอย่างสองชุดแรก สังเกตว่าในกรณีที่ 2 พัลส์ที่สองใช้เพียงสถานี $2$ ร่วมกับพัลส์แรก ซึ่งเป็นไปตามกฎการไม่แทรกสอด
ข้อมูลนำเข้า
มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แสดงจำนวนชุดข้อมูลทดสอบ สำหรับแต่ละชุดข้อมูลทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 3 \times 10^5$) คือจำนวนสถานีในโครงข่าย
สำหรับ $(n - 1)$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสองจำนวน $u_i$ และ $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) อธิบายสายไฟเบอร์ออปติกสองทิศทางระหว่างสถานี $u_i$ และสถานี $v_i$
รับประกันว่าสายเชื่อมต่อทั้งหมดก่อตัวเป็นต้นไม้ และผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $3 \times 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลจำนวนเส้นทางน้อยที่สุด $k$ ในบรรทัดแรก หลังจากนั้นให้แสดงผล $k$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ แทนจุดปลายของเส้นทางที่ $i$ ในลำดับ สังเกตว่า $a_i$ อาจเท่ากับ $b_i$ ได้หากเส้นทางนั้นประกอบด้วยสถานีเพียงสถานีเดียว
หากมีลำดับที่เหมาะสมที่สุดหลายแบบ ลำดับใดก็ได้ที่ปฏิบัติตามโปรโตคอลการไม่แทรกสอดอย่างเคร่งครัดจะได้รับการยอมรับ
ตัวอย่าง
ข้อมูลนำเข้า
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
ข้อมูลส่งออก
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5