מצא את מספר העצים הבינאריים (עץ בינארי הוא עץ מושרש שבו לכל צומת יש לכל היותר בן שמאלי אחד ולכל היותר בן ימני אחד) עם $N$ צמתים הממוספרים $1, 2, \dots, N$ המקיימים את כל התנאים הבאים, והדפס את התוצאה מודולו $998244353$.
- עבור כל $i = 1, 2, \dots, N$, אינדקס הסריקה התחילי (preorder index) של צומת $i$ הוא $i$. בפרט, צומת $1$ הוא השורש.
- עבור כל $i = 1, 2, \dots, M$, אינדקס הסריקה התוכי (inorder index) של צומת $A_i$ הוא $B_i$.
שני עצים בינאריים נחשבים שונים אם קיים צומת $v$ כך שלפחות אחד מהתנאים הבאים מתקיים:
- הקיום או מספר הצומת של הבן השמאלי של $v$ שונה.
- הקיום או מספר הצומת של הבן הימני של $v$ שונה.
אינדקס הסריקה התחילי ואינדקס הסריקה התוכי של כל צומת $v$ בעץ בינארי מוגדרים בתור הערכים הנרשמים ב-preorder[v] וב-inorder[v], בהתאמה, בעת הרצת dfs(root) בפסאודו-קוד הבא:
pre_cnt = 1; in_cnt = 1
def dfs(v):
preorder[v] = pre_cnt; pre_cnt += 1
if v has a left child:
dfs(left child of v)
inorder[v] = in_cnt; in_cnt += 1
if v has a right child:
dfs(right child of v)קלט
הקלט ניתן בפורמט הבא:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- כל ערכי הקלט הם מספרים שלמים.
- $1 \le M \le N \le 500$
- $1 \le A_i, B_i \le N$
- $A_i \ne A_j$ ($i \ne j$)
- $B_i \ne B_j$ ($i \ne j$)
פלט
הדפס את התשובה בשורה בודדת.
דוגמאות
קלט 1
3 1 2 1
פלט 1
2
קלט 2
5 3 1 3 2 5 4 2
פלט 2
0
קלט 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
פלט 3
550222816
הערה
בדוגמה הראשונה, ישנם בדיוק שני עצים בינאריים המקיימים את התנאים. באחד מהם צומת $1$ הוא השורש, צומת $2$ הוא הבן השמאלי של צומת $1$, וצומת $3$ הוא הבן הימני של צומת $2$. בשני צומת $1$ הוא השורש, צומת $2$ הוא הבן השמאלי של צומת $1$, וצומת $3$ הוא הבן הימני של צומת $1$. אינדקסי הסריקה התחיליים והתוכיים שלהם עקביים עם האילוצים הנתונים.
בדוגמה השנייה, אף עץ בינארי אינו מקיים את התנאים.