Hãy tìm số lượng cây nhị phân (cây nhị phân là một cây có gốc mà trong đó mỗi đỉnh có tối đa một con trái và tối đa một con phải) gồm $N$ đỉnh được đánh số $1, 2, \dots, N$ thỏa mãn tất cả các điều kiện sau, và in ra kết quả theo modulo $998244353$.
- Với mỗi $i = 1, 2, \dots, N$, chỉ số duyệt tiền thứ tự (preorder index) của đỉnh $i$ là $i$. Đặc biệt, đỉnh $1$ là gốc.
- Với mỗi $i = 1, 2, \dots, M$, chỉ số duyệt trung thứ tự (inorder index) của đỉnh $A_i$ là $B_i$.
Hai cây nhị phân được coi là khác nhau nếu tồn tại một đỉnh $v$ sao cho ít nhất một trong các điều kiện sau xảy ra:
- Sự tồn tại hoặc số hiệu đỉnh của con trái của $v$ là khác nhau.
- Sự tồn tại hoặc số hiệu đỉnh của con phải của $v$ là khác nhau.
Chỉ số duyệt tiền thứ tự và chỉ số duyệt trung thứ tự của mỗi đỉnh $v$ trong cây nhị phân được định nghĩa lần lượt là các giá trị được ghi trong preorder[v] và inorder[v] khi thực thi dfs(root) trong mã giả sau:
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)Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Tất cả các giá trị đầu vào đều là số nguyên.
- $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$)
Kết quả
In ra câu trả lời trên một dòng duy nhất.
Ví dụ
Dữ liệu vào 1
3 1 2 1
Kết quả 1
2
Dữ liệu vào 2
5 3 1 3 2 5 4 2
Kết quả 2
0
Dữ liệu vào 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Kết quả 3
550222816
Giải thích
Trong ví dụ thứ nhất, có đúng hai cây nhị phân thỏa mãn các điều kiện. Một cây có đỉnh $1$ là gốc, đỉnh $2$ là con trái của đỉnh $1$, và đỉnh $3$ là con phải của đỉnh $2$. Cây còn lại có đỉnh $1$ là gốc, đỉnh $2$ là con trái của đỉnh $1$, và đỉnh $3$ là con phải của đỉnh $1$. Các chỉ số duyệt tiền thứ tự và trung thứ tự của chúng đều phù hợp với các ràng buộc đã cho.
Trong ví dụ thứ hai, không có cây nhị phân nào thỏa mãn các điều kiện.