กำหนดต้นไม้ไม่มีรากที่มี $n$ จุดยอด คุณต้องกำหนดน้ำหนักที่แตกต่างกันให้กับแต่ละจุดยอด โดยน้ำหนักเหล่านั้นประกอบกันเป็นการเรียงสับเปลี่ยนของตัวเลขตั้งแต่ $1$ ถึง $n$
สำหรับรูปแบบการกำหนดน้ำหนักใด ๆ เราจะพิจารณาเส้นผ่านศูนย์กลางทั้งหมดของต้นไม้ (กล่าวคือ วิถีเชิงเดียวที่ยาวที่สุดในต้นไม้) ในบรรดาเส้นผ่านศูนย์กลางเหล่านี้ เราจะเลือกเส้นที่มีลำดับน้ำหนักที่มากที่สุดตามลำดับพจนานุกรม (โดยเรียงน้ำหนักของจุดยอดตามลำดับบนวิถีแล้วเปรียบเทียบตามลำดับพจนานุกรม)
เป้าหมายของคุณคือการทำให้มีค่าน้อยที่สุดสำหรับลำดับพจนานุกรมของลำดับน้ำหนักที่สอดคล้องกับ "เส้นผ่านศูนย์กลางที่มากที่สุดตามลำดับพจนานุกรม" นี้ จากรูปแบบการกำหนดน้ำหนักที่เป็นไปได้ทั้งหมด
ข้อมูลนำเข้า
หนึ่งชุดทดสอบประกอบด้วยหลายกลุ่มข้อมูล
บรรทัดแรกของข้อมูลนำเข้าคือจำนวนกลุ่มข้อมูล $T$ ($1 \le T \le 10^5$) ซึ่งแทนจำนวนกลุ่มข้อมูลในชุดทดสอบนี้
สำหรับแต่ละกลุ่มข้อมูล บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 2 \cdot 10^5$) ซึ่งระบุจำนวนจุดยอด
อีก $n - 1$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน $u, v$ ($1 \le u, v \le n$) ซึ่งแทนเส้นเชื่อมของต้นไม้
รับประกันว่าในทุกกลุ่มข้อมูล $\sum n \le 2 \cdot 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูล ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหลายจำนวน ซึ่งแทนลำดับพจนานุกรมที่น้อยที่สุดที่เป็นไปได้ของเส้นผ่านศูนย์กลางที่มีลำดับพจนานุกรมมากที่สุด
ตัวอย่าง
ข้อมูลนำเข้า
5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 1 4 6 1 2 1 3 2 4 2 5 3 6 8 1 2 2 3 1 4 2 5 3 6 1 7 7 8 10 1 2 2 3 2 4 4 7 4 8 1 5 5 6 6 9 1 10
ข้อมูลส่งออก
3 4 5 1 3 4 2 3 4 5 6 1 2 3 4 5 6 1 3 4 5 6 7 8 1