กำหนดต้นไม้แบบมีรากที่มีจุดยอด $n$ จุด และคู่อันดับ $(x_i,y_i)$ จำนวน $m$ คู่ โดย $x_i,y_i$ เป็นจุดยอดของต้นไม้

สำหรับจุดยอด $a,b$ ของต้นไม้ นิยาม $D(a,b)$ เป็นจำนวนจุดยอดที่อยู่ในต้นไม้ย่อยที่มีรากเป็น $a$ แต่ไม่อยู่ในต้นไม้ย่อยที่มีรากเป็น $b$

คุณต้องหาต้นไม้แผ่ทั่วที่มีน้ำหนักน้อยที่สุดของกราฟบริบูรณ์ที่มีคู่อันดับเหล่านี้เป็นจุดยอด โดยน้ำหนักของเส้นเชื่อมระหว่าง $(x_i,y_i)$ กับ $(x_j,y_j)$ คือ $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$

ข้อมูลนำเข้า

อ่านข้อมูลจากอินพุตมาตรฐาน

บรรทัดแรกมีจำนวนสองจำนวน ระบุ $n,m$

บรรทัดถัดมามีจำนวน $n-1$ จำนวน โดยจำนวนที่ $i$ ระบุพ่อของจุดยอดหมายเลข $i+1$ ซึ่งคือ $f_{i+1}$ รับประกันว่า $f_{i+1}< i+1$

จากนั้นมี $m$ บรรทัด โดยบรรทัดที่ $i$ มีจำนวนสองจำนวน $x_i,y_i$ ระบุคู่อันดับที่กำหนดให้หนึ่งคู่

ข้อมูลส่งออก

ส่งผลลัพธ์ไปยังเอาต์พุตมาตรฐาน

แสดงจำนวนเต็มหนึ่งจำนวน ซึ่งเป็นผลรวมของน้ำหนักเส้นเชื่อมในต้นไม้แผ่ทั่วที่มีน้ำหนักน้อยที่สุด

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

7

หมายเหตุ

ต้นไม้แผ่ทั่วที่มีน้ำหนักน้อยที่สุดประกอบด้วยเส้นเชื่อม $(1,4,1),(2,3,3),(2,4,3)$ โดยแต่ละสามอันดับระบุหมายเลขของคู่อันดับแรก หมายเลขของคู่อันดับที่สอง และน้ำหนักเส้นเชื่อม ผลรวมน้ำหนักเส้นเชื่อมเท่ากับ $7$

งานย่อย

สำหรับข้อมูล $10\%$ มี $1\le n,m\le 1000$

สำหรับข้อมูลอีก $10\%$ มี $1\le m\le 2\times 10^4$

สำหรับข้อมูลอีก $10\%$ มี $1\le m\le 5\times 10^4$

สำหรับข้อมูลอีก $20\%$ มี $m=n^2$ และคู่อันดับทุกคู่แตกต่างกัน

สำหรับข้อมูลอีก $10\%$ สำหรับทุก $i=2\cdots n$ มี $f_i=i-1$

สำหรับข้อมูลอีก $10\%$ สำหรับทุก $i=2\cdots n$ มี $f_i=1$

สำหรับข้อมูล $100\%$ มี $1\le n\le 10^6,1\le m\le 10^5$ สำหรับทุก $i=1,2,\dots n-1$ มี $1\le f_{i+1} < i+1$ สำหรับทุก $i=1,2,\dots m$ มี $1\le x_i,y_i\le n$