רמז: בפסקה האחרונה של תיאור הבעיה מופיע ניסוח פורמלי קצר שלה.

בעתיד הרחוק גילו הפיזיקאים סוף סוף את חוקי הטבע של הזמן והסיבתיות. עוד לפני שאדם נולד, ניתוח תאורטי מאפשר לדעת פרטים מסוימים על חייו. במילים אחרות, הפיזיקה מאפשרת לנו ״לנבא״ במידה מסוימת את ״גורלו״ של אדם.

בפשטות, גורלו של אדם הוא עץ מושרש $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\neq v$, ו־$u$ הוא אב קדמון של $v$. מתמטית, חוויה כזאת מסומנת בזוג הסדור $(u,v)$, וקבוצת כל חוויות החיים הפוטנציאליות בעץ $T$ מסומנת $\mathcal P_T$.

התאוריה הפיזיקלית מאפשרת לנו לצפות בעץ המייצג את הגורל, וגם לנתח אם חוויות חיים פוטנציאליות מסוימות הן ״חשובות״. כל בחירה שאדם עושה, כלומר כל קשת בעץ, עשויה להיות חשובה או לא חשובה. חוויית חיים פוטנציאלית חשובה אם ורק אם יש במסלול המתאים לה קשת חשובה. אנו יכולים לצפות בכך שחוויות פוטנציאליות מסוימות חשובות: כלומר, מתקבלת קבוצה $\mathcal Q\subseteq\mathcal P_T$ שכל חוויה $(u,v)\in\mathcal Q$ בה חשובה.

צורת העץ $T$ כבר חושבה ונקבעה, והקבוצה $\mathcal Q$ כבר נצפתה. אי־הוודאות בגורלו של אדם כבר פחתה מאוד, אך היא עדיין עצומה. הבה נחשב: עבור העץ $T$ והקבוצה $\mathcal Q$ הנתונים, בכמה דרכים שונות אפשר לקבוע עבור כל קשת אם היא חשובה, כך שכל המגבלות שנצפו יתקיימו? כלומר, לכל $(u,v)\in\mathcal Q$, לפחות קשת אחת במסלול מ־$u$ ל־$v$ תיקבע כחשובה.

באופן פורמלי: נתונים עץ $T=(V,E)$ וקבוצת זוגות צמתים $\mathcal Q\subseteq V\times V$, כך שלכל $(u,v)\in\mathcal Q$ מתקיים $u\neq v$, ו־$u$ הוא אב קדמון של $v$ בעץ $T$. הקבוצות $V,E$ הן בהתאמה קבוצת הצמתים וקבוצת הקשתות. מצאו כמה פונקציות שונות $f:E\to\{0,1\}$ קיימות, כלומר השמות ערך $0$ או $1$ לכל קשת $e\in E$, כך שלכל $(u,v)\in\mathcal Q$ קיימת קשת $e$ במסלול מ־$u$ ל־$v$ שעבורה $f(e)=1$. מכיוון שהתשובה עלולה להיות גדולה מאוד, יש להדפיס אותה מודולו $998{,}244{,}353$, שהוא מספר ראשוני.

קלט

יש לקרוא את הנתונים מהקובץ 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\mathcal Q$. שימו לב: הקלט עשוי לכלול מידע חוזר, כלומר ייתכנו $i\neq 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$ אפשרויות, ושש האפשרויות הבאות אינן מקיימות את דרישות הבעיה:

• הקשתות $(1,2),(2,3),(3,5)$ אינן חשובות, ו־$(3,4)$ חשובה: אף מגבלה ב־$\mathcal Q$ אינה מתקיימת.
• הקשתות $(1,2),(2,3),(3,4),(3,5)$ אינן חשובות: אף מגבלה ב־$\mathcal Q$ אינה מתקיימת.
• הקשתות $(1,2),(2,3)$ אינן חשובות, ו־$(3,4),(3,5)$ חשובות: המגבלה $(1,3)$ ב־$\mathcal Q$ אינה מתקיימת.
• הקשתות $(1,2),(2,3),(3,4)$ אינן חשובות, ו־$(3,5)$ חשובה: המגבלה $(1,3)$ ב־$\mathcal Q$ אינה מתקיימת.
• הקשתות $(2,3),(3,5)$ אינן חשובות, ו־$(1,2),(3,4)$ חשובות: המגבלה $(2,5)$ ב־$\mathcal Q$ אינה מתקיימת.
• הקשתות $(2,3),(3,4),(3,5)$ אינן חשובות, ו־$(1,2)$ חשובה: המגבלה $(2,5)$ ב־$\mathcal Q$ אינה מתקיימת.
• בכל יתר האפשרויות, כל המגבלות ב־$\mathcal 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$.

עץ בינארי שלם: בשאלה זו, עץ שבו לכל צומת שאינו עלה יש ילד שמאלי וילד ימני, וכל העלים באותו עומק, נקרא עץ בינארי מושלם. אם ממספרים את צמתי העץ המושלם מלמעלה למטה ומשמאל לימין, העץ המורכב מכמה מהצמתים בעלי המספרים הקטנים ביותר נקרא עץ בינארי שלם.