AT_utpc2025_b Binary Tree Counting

有 $N$ 个顶点，编号为 $1, 2, \dots, N$，请你求满足以下所有条件的二叉树的个数，并将答案对 $998244353$ 取模： - 对于每个 $i = 1, 2, \dots, N$，顶点 $i$ 的**先序遍历编号**为 $i$。特别地，顶点 $1$ 是根节点。 - 对于每个 $i = 1, 2, \dots, M$，顶点 $A_i$ 的**中序遍历编号**为 $B_i$。 这里，当存在某个顶点 $v$ 满足以下任一条件时，认为两棵二叉树不同： - $v$ 的左儿子是否存在或其顶点编号不同。 - $v$ 的右儿子是否存在或其顶点编号不同。 二叉树定义如下：每个顶点至多有一个左儿子和至多有一个右儿子的有根树。 关于先序遍历和中序遍历，定义如下。对于任一顶点 $v$，其在先序、中序遍历中的编号分别在以下伪代码中 `dfs(根)` 执行时得到 `preorder[v]` 与 `inorder[v]` 的值： ``` pre_cnt = 1; in_cnt = 1 def dfs(v): preorder[v] = pre_cnt; pre_cnt += 1 if v 的左儿子存在: dfs(v 的左儿子) inorder[v] = in_cnt; in_cnt += 1 if v 的右儿子存在: dfs(v 的右儿子) ```

输入格式如下，通过标准输入读入： > $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出一行，表示满足条件的二叉树个数对 $998244353$ 取模的结果。

### 样例解释 1 有以下两棵满足条件的二叉树： - 顶点 $1$ 为根，顶点 $2$ 是顶点 $1$ 的左儿子，顶点 $3$ 是顶点 $2$ 的右儿子。对此二叉树， - 顶点 $1$ 的先序编号是 $1$，中序编号是 $3$。 - 顶点 $2$ 的先序编号是 $2$，中序编号是 $1$。 - 顶点 $3$ 的先序编号是 $3$，中序编号是 $2$。 - 顶点 $1$ 为根，顶点 $2$ 是顶点 $1$ 的左儿子，顶点 $3$ 是顶点 $1$ 的右儿子。对此二叉树， - 顶点 $1$ 的先序编号是 $1$，中序编号是 $2$。 - 顶点 $2$ 的先序编号是 $2$，中序编号是 $1$。 - 顶点 $3$ 的先序编号是 $3$，中序编号是 $3$。 ### 样例解释 2 不存在符合条件的二叉树。 ### 数据范围 - 输入均为整数。 - $1 \leq M \leq N \leq 500$ - $1 \leq A_i, B_i \leq N$ - $A_i \neq A_j\ (i \neq j)$ - $B_i \neq B_j\ (i \neq j)$ 由 ChatGPT 5 翻译