Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Find the number of binary trees (a binary tree is a rooted tree in which each vertex has at most one left child and at most one right child) with $N$ vertices labeled $1, 2, \dots, N$ that satisfy all of the following conditions, and output the result modulo $998244353$.

  • For each $i = 1, 2, \dots, N$, the preorder index of vertex $i$ is $i$. In particular, vertex $1$ is the root.
  • For each $i = 1, 2, \dots, M$, the inorder index of vertex $A_i$ is $B_i$.

Two binary trees are considered different if there exists a vertex $v$ such that at least one of the following holds:

  • The existence or the vertex number of the left child of $v$ is different.
  • The existence or the vertex number of the right child of $v$ is different.

The preorder index and inorder index of each vertex $v$ in a binary tree are defined as the values recorded in preorder[v] and inorder[v], respectively, when executing dfs(root) in the following pseudocode:

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)

Input

The input is given in the following format:

$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$

  • All input values are integers.
  • $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$)

Output

Output the answer on a single line.

Examples

Input 1

3 1
2 1

Output 1

2

Input 2

5 3
1 3
2 5
4 2

Output 2

0

Input 3

30 6
12 26
9 5
15 14
19 15
4 2
10 4

Output 3

550222816

Note

In the first example, there are exactly two binary trees that satisfy the conditions. One has vertex $1$ as the root, vertex $2$ as the left child of vertex $1$, and vertex $3$ as the right child of vertex $2$. The other has vertex $1$ as the root, vertex $2$ as the left child of vertex $1$, and vertex $3$ as the right child of vertex $1$. Their preorder and inorder indices are consistent with the given constraints.

In the second example, no binary tree satisfies the conditions.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1406EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.