CF1929F.Sasha and the Wedding Binary Search Tree

Having overcome all the difficulties and hardships, Sasha finally decided to marry his girlfriend. To do this, he needs to give her an engagement ring. However, his girlfriend does not like such romantic gestures, but she does like binary search trees$^{\dagger}$. So Sasha decided to give her such a tree.

After spending a lot of time on wedding websites for programmers, he found the perfect binary search tree with the root at vertex $1$. In this tree, the value at vertex $v$ is equal to $val_v$.

But after some time, he forgot the values in some vertices. Trying to remember the found tree, Sasha wondered — how many binary search trees could he have found on the website, if it is known that the values in all vertices are integers in the segment $[1, C]$. Since this number can be very large, output it modulo $998\,244\,353$.

$^{\dagger}$A binary search tree is a rooted binary tree in which for any vertex $x$, the following property holds: the values of all vertices in the left subtree of vertex $x$ (if it exists) are less than or equal to the value at vertex $x$, and the values of all vertices in the right subtree of vertex $x$ (if it exists) are greater than or equal to the value at vertex $x$.

在克服了所有困难与艰辛之后，萨沙终于决定迎娶他的女友。为此，他需要送她一枚订婚戒指。然而，他的女友并不喜欢这种浪漫的举动，但她却钟爱二叉搜索树$^{\dagger}$。于是萨沙决定送她这样一棵二叉搜索树。

他在程序员专用的婚礼网站上花费了大量时间，最终找到了一棵完美的二叉搜索树，其根节点为顶点 $1$。在这棵树中，顶点 $v$ 处的值为 $val_v$。

但过了一段时间后，他忘记了某些顶点上的数值。为了努力回忆起这棵已找到的树，萨沙不禁思考：若已知所有顶点上的值均为区间 $[1, C]$ 内的整数，则该网站上可能存在的满足条件的二叉搜索树一共有多少棵？由于这个数目可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

$^{\dagger}$ 二叉搜索树是一棵有根二叉树，满足如下性质：对任意顶点 $x$，其左子树（若存在）中所有顶点的值均小于或等于顶点 $x$ 的值，而其右子树（若存在）中所有顶点的值均大于或等于顶点 $x$ 的值。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $C$ ($2 \leq n \leq 5 \cdot 10^5$, $1 \leq C \leq 10^9$) — the number of vertices in the tree and the maximum allowed value at the vertex.

The next $n$ lines describe the vertices of the tree. The $i$-th line contains three integers $L_i, R_i$ and $val_i$ ($-1 \le L_i, R_i \le n$, $-1 \le val_i \le C$, $L_i, R_i, val_i \ne 0$) — the number of the left child, the number of the right child, and the value at the $i$-th vertex, respectively. If $L_i = -1$, then the $i$-th vertex has no left son. If $R_i = -1$, then the $i$-th vertex has no right son. If $val_i = -1$, then the value at the $i$-th vertex is unknown.

It is guaranteed that at least one suitable binary search tree exists.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $C$（$2 \leq n \leq 5 \cdot 10^5$，$1 \leq C \leq 10^9$），分别表示树中顶点的数量以及顶点上允许的最大值。

接下来的 $n$ 行描述树的各个顶点。第 $i$ 行包含三个整数 $L_i$、$R_i$ 和 $val_i$（$-1 \le L_i, R_i \le n$，$-1 \le val_i \le C$，且 $L_i, R_i, val_i \ne 0$），分别表示第 $i$ 个顶点的左子节点编号、右子节点编号以及该顶点上的值。若 $L_i = -1$，则第 $i$ 个顶点无左子节点；若 $R_i = -1$，则第 $i$ 个顶点无右子节点；若 $val_i = -1$，则第 $i$ 个顶点上的值未知。

保证至少存在一棵满足条件的二叉搜索树。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

For each test case, output a single integer — the number of suitable binary search trees modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——满足条件的二叉搜索树的数量对 $998\,244\,353$ 取模的结果。

In the first test case, the binary search tree has the following form:

Then the possible values at the vertices are: $[2, 2, 3, 2, 2]$, $[2, 2, 3, 2, 3]$, $[2, 2, 3, 3, 3]$, and $[3, 2, 3, 3, 3]$.

In the second test case, the values at all vertices are known, so there is only one suitable binary search tree.

在第一个测试用例中，二叉搜索树具有如下结构：

此时，各顶点可能的取值为：$[2, 2, 3, 2, 2]$、$[2, 2, 3, 2, 3]$、$[2, 2, 3, 3, 3]$ 和 $[3, 2, 3, 3, 3]$。

在第二个测试用例中，所有顶点的值均已确定，因此仅存在唯一一棵满足条件的二叉搜索树。