暂无测试数据。

Description

猴国打算种一批树。所谓树，就是由 \(N\) 个结点与 \(N–1\) 条边连接而成的连通无向。猴国的国王 \(\text{Scarral}\) 对于这些树有下列要求：
1. 树没有指定根，但它的形态是给定（即这 \(N–1\) 条边是给出的）；
2. 树的每条边上可以放置一朵花（当然也可以不放置）；
3. 共 \(Q\) 条约束，第 \(i\) 组约束规定：标号 \(u_i\) 的结点到标号 \(v_i\) 的结点的简单路径上，花的数量为奇数或偶数。

现在，国王想事先知道他最多能种多少棵不一样的树（两棵树被视为不一样当且仅一棵树中某条边的放花情况与另一棵树不相同）。

Input

第 \(1\) 行两个整数 \(N\)，\(Q\)；
接下来 \(N–1\) 行，每行两个整数 \(u\)、\(v\)，表示 \(u\)、\(v\) 间存在一条边；
接下来 \(Q\) 行，每三个整数 \(u_i\)、\(v_i\)、\(k_i\)，若 \(k_i\) 为 \(1\)，表示 \(u_i\) 到 \(v_i\)的简单路径的上花的个数为奇数，否则为偶数。

Output

一行一个整数，表示能种的不一样的树的种树，对 \(998244353\) 取模。

Sample

Sample input

5 3
1 2
1 3
2

Sample output

2 4
2 5
1 4 0
1 5 1
1 3 0

Hint

\(20\%\) 的数据：\(N,\ Q\leq 20\)；
\(40\%\) 的数据：\(N,\ Q\leq 100\)；
\(70\%\) 的数据：\(N,\ Q\leq 5000\)；
\(100\%\) 的数据：\(N,\ Q\leq 100000\)、\(0\leq k_i\leq 1\)。