กำหนดต้นไม้ไม่มีรากที่มี $n$ โหนด โดยแต่ละโหนดมีสีซึ่งแทนด้วยจำนวนเต็มบวก $c_i$ สำหรับโหนดที่ $i$

สมมติว่า $S$ และ $T$ เป็นเซตของโหนดในต้นไม้ คู่อันดับ $(S, T)$ จะถือว่าถูกต้องหากเป็นไปตามเงื่อนไขต่อไปนี้ทั้งหมด:

• ทั้ง $S$ และ $T$ เป็นเซตไม่ว่าง
• โหนดทั้งหมดใน $S$ มีสีเดียวกัน และโหนดทั้งหมดใน $T$ มีสีเดียวกัน
• กราฟย่อย $\text{sub}(S)$ ของเซตของโหนด $S$ นิยามว่าเป็น กราฟย่อยเชื่อมโยงที่เล็กที่สุด ของต้นไม้ที่มีเซตของโหนด $S$ อยู่ และนิยามในทำนองเดียวกันสำหรับ $\text{sub}(T)$ โดยกำหนดว่า $\text{sub}(S)$ และ $\text{sub}(T)$ ต้องไม่ตัดกัน กล่าวคือไม่มีโหนดหรือเส้นเชื่อมร่วมกันเลย

จงหาจำนวนของคู่อันดับ $(S, T)$ ที่ถูกต้องทั้งหมด มอดุโล $998244353$ โปรดสังเกตว่าถ้า $S \neq T$ คู่อันดับ $(S, T)$ จะถือว่าแตกต่างจากคู่อันดับ $(T, S)$

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

โจทย์ข้อนี้มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ:

บรรทัดแรกมีจำนวนเต็ม $n$ ($1 \le n \le 2 \times 10^5$) แทนจำนวนโหนดในต้นไม้ไม่มีราก

บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน คือ $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) แทนสีของแต่ละโหนด

อีก $n - 1$ บรรทัดถัดไป แต่ละบรรทัดมีจำนวนเต็มสองจำนวน คือ $u, v$ ($1 \le u, v \le n, u \neq v$) แทนเส้นเชื่อมของต้นไม้ รับประกันว่าเส้นเชื่อมทั้ง $n - 1$ เส้นนี้ประกอบกันเป็นโครงสร้างต้นไม้

ข้อมูลรับประกันว่าผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบรวมกันไม่เกิน $2 \times 10^5$

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

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน แทนจำนวนคู่อันดับมอดุโล $998244353$

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

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

ข้อมูลส่งออกตัวอย่าง 1

2
54
42