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 翻译