Төмендегі шарттардың барлығын қанағаттандыратын, $1, 2, \dots, N$ деп белгіленген $N$ төбесі бар екілік ағаштардың (екілік ағаш — әрбір төбесінің ең көбі бір сол жақ ұрпағы және ең көбі бір оң жақ ұрпағы болатын түбірлі ағаш) санын табыңыз және нәтижені $998244353$ модулі бойынша шығарыңыз.
- Әрбір $i = 1, 2, \dots, N$ үшін $i$ төбесінің тура аралау индексі (preorder index) $i$-ге тең. Атап айтқанда, $1$ төбесі — түбір.
- Әрбір $i = 1, 2, \dots, M$ үшін $A_i$ төбесінің ішкі аралау индексі (inorder index) $B_i$-ге тең.
Егер келесі шарттардың кемінде біреуі орындалатындай $v$ төбесі табылса, екі екілік ағаш әртүрлі деп есептеледі:
- $v$ төбесінің сол жақ ұрпағының бар-жоғы немесе төбе нөмірі өзгеше.
- $v$ төбесінің оң жақ ұрпағының бар-жоғы немесе төбе нөмірі өзгеше.
Екілік ағаштағы әрбір $v$ төбесінің тура аралау индексі мен ішкі аралау индексі төмендегі псевдокодта dfs(root) орындалған кезде сәйкесінше preorder[v] және inorder[v] массивтеріне жазылатын мәндер ретінде анықталады:
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$ төбесінің оң жақ ұрпағы. Олардың тура және ішкі аралау индекстері берілген шектеулерге сәйкес келеді.
Екінші мысалда ешбір екілік ағаш шарттарды қанағаттандырмайды.