久莲 เป็นเด็กหญิงที่ชอบออกโจทย์
หลังการแข่งขัน World Final ในปีนี้จบลง 久莲 ชอบเรขาคณิตเชิงคำนวณเป็นพิเศษ จึงตั้งใจจะออกโจทย์เรขาคณิตเชิงคำนวณในสนามสอบ NOI ด้วย นี่คือโจทย์ที่มีเพียงชื่อเกี่ยวข้องกับเรขาคณิตเชิงคำนวณเท่านั้น
เริ่มแรก 久莲 ให้ต้นไม้มีราก $T$ ที่มี $n$ โหนด ($n\ge2$) โดยรากมีหมายเลข $1$ นิยามโหนดใบว่าเป็นโหนดที่ไม่ใช่รากและมีดีกรีเท่ากับ $1$ พอดี ภาพต่อไปนี้คือตัวอย่างต้นไม้ $T$ ซึ่งมีเซตโหนดใบเป็น $\{3,4,5\}$
จากต้นไม้นี้ 久莲 สร้างลำดับ $A$ ดังนี้:
- ท่องต้นไม้ทั้งต้นแบบค้นตามลึก โดยเริ่มจากราก และเยี่ยมลูกตามหมายเลขจากน้อยไปมาก ซึ่งจะได้ลำดับ DFS ของต้นไม้ $T$
- จากนั้น 久莲 นำโหนดใบทั้งหมดมาเรียงตามลำดับที่ปรากฏในลำดับ DFS จากหน้าไปหลัง ได้เป็นลำดับ $A$
จากลำดับ $A$ นี้ 久莲 นิยามระยะทาง $d(u,v)$ ระหว่างโหนดใบสองโหนด $u,v$ ดังนี้: สมมติว่า $u$ เป็นสมาชิกตำแหน่งที่ $i$ และ $v$ เป็นสมาชิกตำแหน่งที่ $j$ ใน $A$ ให้ $d(u,v)=\min(|i-j|,|A|-|i-j|)$ โดย $|A|$ คือความยาวลำดับ หรือก็คือจำนวนโหนดใบของ $T$ และ $i,j$ คือตำแหน่งที่ปรากฏ เริ่มนับจาก $1$
ในตัวอย่างข้างต้น ลำดับ $A$ คือ $[4,5,3]$ โดย $d(3,5)=d(3,4)=d(4,5)=1$ และตำแหน่งที่ $3,4,5$ ปรากฏคือ $3,1,2$ ตามลำดับ
สุดท้าย 久莲 ให้พารามิเตอร์ $K$ เราสามารถใช้ต้นไม้มีราก $T$ และลำดับ $A$ สร้างกราฟไม่มีทิศทาง $G$ ที่มี $n$ โหนด ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวนที่โหนดเดียว โดยโหนดที่แตกต่างกันสองโหนด $u,v$ มีเส้นเชื่อมระหว่างกันก็ต่อเมื่อเป็นไปตามเงื่อนไขต่อไปนี้อย่างน้อยหนึ่งข้อ:
- ในต้นไม้ $T$ มีเส้นเชื่อมระหว่าง $u,v$
- ในต้นไม้ $T$ ทั้ง $u,v$ เป็นโหนดใบ และ $d(u,v)\le K$
เมื่อ $K=1$ หรือ $2$ กราฟ $G$ ที่ได้จากตัวอย่างข้างต้นเป็นดังภาพต่อไปนี้ทั้งสองกรณี
ตอนนี้ 久莲 ต้องการให้คุณนับว่าใน $G$ มีวงจรแฮมิลตันที่แตกต่างกันกี่วง คำตอบอาจมีค่ามาก ให้ส่งออกผลลัพธ์เมื่อหารเอาเศษด้วย $998244353$
ต่อไปนี้เป็นนิยามเพิ่มเติม:
- วงจรแฮมิลตัน $H$ ของกราฟไม่มีทิศทาง $G$ ที่ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวนที่โหนดเดียว คือสับเซตของเส้นเชื่อมใน $G$ ซึ่งแต่ละโหนดมีเส้นเชื่อมที่แตกต่างกันและติดกับมันอยู่ใน $H$ พอดีสองเส้น และโหนดสองโหนดใด ๆ สามารถเดินทางถึงกันโดยตรงหรือโดยอ้อมผ่านเส้นเชื่อมใน $H$ ได้
- วงจรแฮมิลตันสองวง $H_1,H_2$ ของกราฟไม่มีทิศทาง $G$ ที่ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวนที่โหนดเดียว แตกต่างกันก็ต่อเมื่อมีเส้นเชื่อม $e$ ซึ่งอยู่ใน $H_1$ แต่ไม่อยู่ใน $H_2$
ข้อมูลนำเข้า
อ่านข้อมูลจากไฟล์ polygon.in
บรรทัดแรกมีจำนวนเต็มสองจำนวน $n,K$ ระบุจำนวนโหนดในต้นไม้ $T$ และพารามิเตอร์ $K$ ที่ 久莲 เลือก
บรรทัดที่สองมีจำนวนเต็ม $n-1$ จำนวน $f_i$ ($1\le f_i\le i$) โดย $f_i$ ระบุว่าต้นไม้ $T$ มีเส้นเชื่อม $(f_i,i+1)$
ข้อมูลส่งออก
ส่งออกไปยังไฟล์ polygon.out
ส่งออกหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน ระบุจำนวนวงจรแฮมิลตันเมื่อหารเอาเศษด้วย $998244353$
ตัวอย่าง
ข้อมูลนำเข้า 1
5 1 1 1 2 2
ข้อมูลส่งออก 1
2
หมายเหตุ
ตัวอย่างนี้ตรงกับตัวอย่างในโจทย์ทุกประการ ลำดับโหนดที่วงจรแฮมิลตันทั้งสองผ่านคือ $(1,2,4,5,3)$ และ $(1,2,5,4,3)$ ตามลำดับ
งานย่อย
ขนาดและคุณสมบัติของข้อมูลแต่ละกรณีทดสอบแสดงในตารางต่อไปนี้:
| หมายเลข | $n$ | $K$ | คุณสมบัติพิเศษ |
|---|---|---|---|
| $1$ | $\le5$ | $\le3$ | ไม่มี |
| $2$ | $\le10$ | $\le3$ | ไม่มี |
| $3$ | $\le15$ | $\le3$ | ไม่มี |
| $4$ | $\le20$ | $\le3$ | ไม่มี |
| $5$ | $\le1000$ | $=1$ | A |
| $6$ | $\le1000$ | $=1$ | A |
| $7$ | $\le1000$ | $=1$ | A |
| $8$ | $\le1000$ | $=1$ | ไม่มี |
| $9$ | $\le1000$ | $=1$ | ไม่มี |
| $10$ | $\le1000$ | $=1$ | ไม่มี |
| $11$ | $\le1000$ | $\le2$ | A |
| $12$ | $\le1000$ | $\le2$ | A |
| $13$ | $\le1000$ | $\le2$ | A |
| $14$ | $\le1000$ | $\le2$ | ไม่มี |
| $15$ | $\le1000$ | $\le2$ | ไม่มี |
| $16$ | $\le1000$ | $\le2$ | ไม่มี |
| $17$ | $\le1000$ | $\le3$ | A |
| $18$ | $\le1000$ | $\le3$ | A |
| $19$ | $\le1000$ | $\le3$ | ไม่มี |
| $20$ | $\le1000$ | $\le3$ | ไม่มี |
คุณสมบัติ A รับประกันว่าทุกโหนดในต้นไม้มีลูกไม่เกินสองโหนด
สำหรับข้อมูลทั้งหมด รับประกันว่า $1\le f_i\le i$, $2\le n\le1000$