คำแนะนำ: ในย่อหน้าสุดท้ายของคำอธิบายโจทย์ เราได้ให้คำอธิบายแบบเป็นทางการอย่างย่อไว้

ในอนาคตอันไกลโพ้น ในที่สุดนักฟิสิกส์ก็ค้นพบกฎธรรมชาติของเวลาและเหตุผล แม้ก่อนที่คนคนหนึ่งจะเกิด เราก็สามารถรู้ข้อมูลบางอย่างเกี่ยวกับชีวิตของเขาหรือเธอได้จากการวิเคราะห์เชิงทฤษฎี กล่าวอีกนัยหนึ่ง ฟิสิกส์ทำให้เราสามารถ “ทำนาย” “ชะตากรรม” ของคนคนหนึ่งได้ในระดับหนึ่ง

พูดอย่างง่าย ชะตากรรมของคนคนหนึ่งคือต้นไม้มีราก $T$ ที่ประกอบด้วยจุดเวลา: รากของต้นไม้แทนการเกิด และใบแทนการตาย โหนดที่ไม่ใช่ใบแต่ละโหนด $u$ มีลูกหนึ่งโหนดหรือมากกว่า คือ $v_1,v_2,\ldots,v_{c_u}$ ซึ่งแทนความเป็นไปได้ต่าง ๆ ที่เกิดจากทางเลือกที่แตกต่างกัน $c_u$ ทางของคนคนนั้น ณ เวลาที่ $u$ แทนอยู่ กล่าวอย่างเป็นทางการ ทางเลือก คือเส้นเชื่อม $(u,v_i)$ ในต้นไม้ โดย $u$ เป็นโหนดพ่อแม่ของ $v_i$

ชีวิตของคนคนหนึ่งคือเส้นทางจากการเกิด (ราก) ไปยังการตาย (โหนดใบโหนดหนึ่ง) โดยไม่ผ่านโหนดใดซ้ำ เส้นทางย่อยใด ๆ ของเส้นทางนี้ที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นคือ ประสบการณ์ชีวิต ช่วงหนึ่งของคนคนนั้น และประสบการณ์ชีวิตทั้งหมดที่เขาหรือเธออาจมีจากการใช้ชีวิตในทุกวิถีทางที่เป็นไปได้ เรียกว่า ประสบการณ์ชีวิตที่เป็นไปได้ กล่าวอีกนัยหนึ่ง ประสบการณ์ชีวิตที่เป็นไปได้ทั้งหมดคือเส้นทางจาก $u$ ไปยัง $v$ ทั้งหมดที่ $u,v\in T$, $u\ne v$ และ $u$ เป็นบรรพบุรุษของ $v$ ในทางคณิตศาสตร์ ประสบการณ์ชีวิตที่เป็นไปได้เช่นนี้เขียนแทนด้วยคู่อันดับ $(u,v)$ และเซตของประสบการณ์ชีวิตที่เป็นไปได้ทั้งหมดของต้นไม้ $T$ เขียนแทนด้วย $P_T$

ทฤษฎีฟิสิกส์ไม่เพียงทำให้เราสังเกตต้นไม้ที่แทนชะตากรรมได้ แต่ยังทำให้เราวิเคราะห์ได้ว่าประสบการณ์ชีวิตที่เป็นไปได้บางช่วงนั้น “สำคัญ” หรือไม่ ทุกทางเลือกที่คนคนหนึ่งเลือก ซึ่งก็คือเส้นเชื่อมแต่ละเส้นในต้นไม้ อาจ สำคัญ หรือ ไม่สำคัญ ประสบการณ์ชีวิตที่เป็นไปได้ช่วงหนึ่งเรียกว่าสำคัญ ก็ต่อเมื่อมีเส้นเชื่อมที่สำคัญอย่างน้อยหนึ่งเส้นบนเส้นทางที่สอดคล้องกัน เราสามารถสังเกตได้ว่าประสบการณ์ชีวิตที่เป็นไปได้บางช่วงนั้นสำคัญ กล่าวอีกนัยหนึ่ง เราสามารถสังเกตได้เซต $Q\subseteq P_T$ ซึ่งประสบการณ์ชีวิตที่เป็นไปได้ทุกคู่ $(u,v)\in Q$ ล้วนสำคัญ

รูปทรงของต้นไม้ $T$ ถูกคำนวณและกำหนดไว้แล้ว และเซต $Q$ ก็ถูกสังเกตไว้แล้วเช่นกัน ความไม่แน่นอนของชะตากรรมของคนคนหนึ่งจึงลดลงอย่างมาก แต่ความไม่แน่นอนก็ยังคงมหาศาล มาลองคำนวณกัน: สำหรับต้นไม้ $T$ และเซต $Q$ ที่กำหนด มีวิธีที่แตกต่างกันกี่วิธีในการกำหนดว่าเส้นเชื่อมแต่ละเส้นสำคัญหรือไม่ โดยเป็นไปตามข้อจำกัดที่สอดคล้องกับ $Q$ ที่สังเกตได้ นั่นคือ สำหรับทุก $(u,v)\in Q$ มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นบนเส้นทางจาก $u$ ไปยัง $v$ ที่ถูกกำหนดให้สำคัญ

คำอธิบายแบบเป็นทางการ: กำหนดต้นไม้ $T=(V,E)$ และเซตของคู่โหนด $Q\subseteq V\times V$ โดยสำหรับทุก $(u,v)\in Q$ มี $u\ne v$ และ $u$ เป็นบรรพบุรุษของ $v$ ในต้นไม้ $T$ ในที่นี้ $V$ และ $E$ แทนเซตของโหนดและเซตของเส้นเชื่อมของต้นไม้ $T$ ตามลำดับ จงหาจำนวนฟังก์ชันที่แตกต่างกัน $f:E\to\{0,1\}$ (กำหนดค่า $f(e)$ เป็น $0$ หรือ $1$ ให้เส้นเชื่อมแต่ละเส้น $e\in E$) ที่ทำให้สำหรับทุก $(u,v)\in Q$ มีเส้นเชื่อม $e$ บนเส้นทางจาก $u$ ไปยัง $v$ ที่ $f(e)=1$ เนื่องจากคำตอบอาจมีขนาดใหญ่มาก ให้ส่งออกเพียงเศษจากการหารคำตอบด้วย $998\,244\,353$ (ซึ่งเป็นจำนวนเฉพาะ)

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

อ่านข้อมูลจากไฟล์ destiny.in

• บรรทัดแรกมีจำนวนเต็มบวก $n$ แทนขนาดของต้นไม้ $T$ โหนดในต้นไม้มีหมายเลขตั้งแต่ $1$ ถึง $n$ และโหนดหมายเลข $1$ เป็นราก
• แต่ละบรรทัดใน $n-1$ บรรทัดถัดมามีจำนวนสองจำนวน $x_i,y_i$ คั่นด้วยช่องว่าง โดย $1\le x_i,y_i\le n$ แสดงว่ามีเส้นเชื่อมระหว่างโหนด $x_i$ และ $y_i$ ในต้นไม้ แต่ไม่รับประกันทิศทางของเส้นเชื่อมนี้
• บรรทัดถัดมามีจำนวนเต็มไม่เป็นลบ $m$ แทนจำนวนข้อมูลที่สังเกตได้
• แต่ละบรรทัดใน $m$ บรรทัดถัดมามีจำนวนสองจำนวน $u_i,v_i$ คั่นด้วยช่องว่าง แสดงว่า $(u_i,v_i)\in Q$ โปรดทราบ: ข้อมูลนำเข้าอาจมีข้อมูลซ้ำกัน กล่าวอีกนัยหนึ่ง อาจมี $i\ne j$ ซึ่ง $u_i=u_j$ และ $v_i=v_j$

ขนาดและข้อจำกัดของข้อมูลนำเข้าแสดงไว้ในตารางท้ายโจทย์

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

ส่งออกไปยังไฟล์ destiny.out

• ส่งออกเพียงหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน แทนเศษจากการหารจำนวนวิธีด้วย $998\,244\,353$

ตัวอย่าง

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

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

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

10

หมายเหตุ

มีทั้งหมด $16$ วิธี โดยมี $6$ วิธีต่อไปนี้ที่ไม่เป็นไปตามเงื่อนไขของโจทย์:

• กำหนดให้ $(1,2),(2,3),(3,5)$ ไม่สำคัญ และ $(3,4)$ สำคัญ: ไม่มีข้อจำกัดใดในเซต $Q$ ที่เป็นจริง
• กำหนดให้ $(1,2),(2,3),(3,4),(3,5)$ ไม่สำคัญ: ไม่มีข้อจำกัดใดในเซต $Q$ ที่เป็นจริง
• กำหนดให้ $(1,2),(2,3)$ ไม่สำคัญ และ $(3,4),(3,5)$ สำคัญ: ข้อจำกัด $(1,3)$ ในเซต $Q$ ไม่เป็นจริง
• กำหนดให้ $(1,2),(2,3),(3,4)$ ไม่สำคัญ และ $(3,5)$ สำคัญ: ข้อจำกัด $(1,3)$ ในเซต $Q$ ไม่เป็นจริง
• กำหนดให้ $(2,3),(3,5)$ ไม่สำคัญ และ $(1,2),(3,4)$ สำคัญ: ข้อจำกัด $(2,5)$ ในเซต $Q$ ไม่เป็นจริง
• กำหนดให้ $(2,3),(3,4),(3,5)$ ไม่สำคัญ และ $(1,2)$ สำคัญ: ข้อจำกัด $(2,5)$ ในเซต $Q$ ไม่เป็นจริง
• สำหรับวิธีอื่น ๆ ข้อจำกัดทั้งหมดในเซต $Q$ เป็นจริง

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

15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13

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

960

ตัวอย่าง 3

ดูไฟล์ destiny/destiny3.in และ destiny/destiny3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่าง 4

ดูไฟล์ destiny/destiny4.in และ destiny/destiny4.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ข้อจำกัด

ข้อมูลทั้งหมดเป็นไปตามเงื่อนไข: $n\le 5\times10^5$, $m\le 5\times10^5$ ข้อมูลนำเข้าประกอบเป็นต้นไม้ และสำหรับ $1\le i\le m$ โหนด $u_i$ เป็นบรรพบุรุษของ $v_i$ เสมอ

ต้นไม้ทวิภาคแบบบริบูรณ์: ในโจทย์นี้ ต้นไม้ที่ทุกโหนดที่ไม่ใช่ใบมีทั้งลูกซ้ายและลูกขวา และโหนดใบทั้งหมดมีความลึกเท่ากัน เรียกว่าต้นไม้ทวิภาคสมบูรณ์ เมื่อกำหนดหมายเลขให้โหนดในต้นไม้ทวิภาคสมบูรณ์จากบนลงล่างและจากซ้ายไปขวา ต้นไม้ที่เกิดจากโหนดจำนวนหนึ่งซึ่งมีหมายเลขน้อยที่สุดเรียกว่าต้นไม้ทวิภาคแบบบริบูรณ์