ملاحظة: نقدم في الفقرة الأخيرة من وصف المسألة صياغة رسمية مختصرة لها.

في المستقبل البعيد، اكتشف الفيزيائيون أخيرًا القوانين الطبيعية للزمن والسببية. وحتى قبل ولادة شخص ما، يمكننا معرفة بعض المعلومات عن حياته بالتحليل النظري؛ وبعبارة أخرى، تسمح لنا الفيزياء إلى حد ما «بالتنبؤ» بـ«مصير» الإنسان.

ببساطة، مصير الإنسان شجرة متجذرة $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$ بـ$\mathcal P_T$.

لا تسمح النظرية الفيزيائية بمشاهدة شجرة المصير فحسب، بل بتحليل ما إذا كانت بعض تجارب الحياة المحتملة «مهمة» أيضًا. كل خيار يتخذه الإنسان، أي كل حافة في الشجرة، قد يكون مهمًا أو غير مهم. وتسمى تجربة محتملة مهمة إذا وفقط إذا وجدت حافة مهمة في مسارها. ويمكننا مشاهدة أن بعض التجارب المحتملة مهمة؛ أي يمكننا الحصول بالمشاهدة على مجموعة $Q\subseteq\mathcal 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$ مجموعتي عقد الشجرة وحوافها على التوالي. أوجد عدد الدوال المختلفة $f:E\to\{0,1\}$، أي تعيين قيمة $f(e)$ لكل حافة $e\in E$ إلى $0$ أو $1$، التي تحقق أنه لكل $(u,v)\in Q$ توجد حافة $e$ في المسار من $u$ إلى $v$ يكون $f(e)=1$. ولأن الإجابة قد تكون كبيرة جدًا، لا يلزمك إلا إخراجها بترديد $998244353$، وهو عدد أولي.

الإدخال

اقرأ البيانات من الملف destiny.in.

• يحتوي السطر الأول على عدد صحيح موجب $n$، يمثل حجم الشجرة $T$. تُرقم العقد من $1$ إلى $n$، والعقدة $1$ هي الجذر.
• تحتوي الأسطر $n-1$ التالية على عددين $x_i,y_i$ مفصولين بفراغ في كل سطر، حيث $1\leq x_i,y_i\leq 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.

• أخرج سطرًا واحدًا فقط يحتوي على عدد صحيح، يمثل عدد الطرق بترديد $998244353$.

أمثلة

الإدخال 1

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

الإخراج 1

10

ملاحظة

هناك $16$ طريقة إجمالًا، والطرق الست التالية لا تحقق شروط المسألة:

• الحواف $(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\leq5\times10^5$ و$m\leq5\times10^5$. يشكل الإدخال شجرة، ولكل $1\leq i\leq m$ تكون $u_i$ دائمًا سلفًا للعقدة $v_i$.

الشجرة الثنائية الكاملة: في هذه المسألة، تسمى الشجرة التي لكل عقدة غير ورقية فيها ابنان أيسر وأيمن، وجميع أوراقها على العمق نفسه، شجرة ثنائية مثالية. إذا رُقمت عقد شجرة ثنائية مثالية من الأعلى إلى الأسفل ومن اليسار إلى اليمين، فإن الشجرة المكونة من عدد من العقد ذات الأرقام الأصغر تسمى شجرة ثنائية كاملة.