植树方案

题目描述

$T$国打算种一批树。所谓树，就是由$n$个结点与$n-1$条边连接而成的连通无向图。$T$国的国王对于这些树有下列要求：

1. 树没有根，但它的形态是给定的（即这$n-1$条边是给出的）；
2. 树的每条边上可以放置一朵花（当然也可以不放置）；
3. 共$Q$条约束，第$i$组约束规定：标号$u_{i}$的结点到标号$v_{i}$的结点的简单路径上，花的数量为奇数或偶数。

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

输入格式

第$1$行，两个整数$n$，$Q$；

接下来$n-1$行，每行两个整数$u$、$v$，表示结点$u$、$v$间存在一条边；

接下来$Q$行，每行三个整数$u_{i}$，$v_{i}$，$k_{i}$。若$k_{i}$为$0$，表示$u_{i}$到$v_{i}$的简单路径上花的数量必须为偶数；若$k_{i}$为$1$，表示$u_{i}$到$v_{i}$的简单路径上花的数量必须为奇数。

输出格式

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

数据范围与提示

• 对于$20\%$的数据，$n$，$Q \leq 20$；
• 对于$40\%$的数据，$n$，$Q \leq 100$；
• 对于$70\%$的数据，$n$，$Q \leq 5000$；
• 对于$100\%$的数据，$1 \leq n$，$Q \leq 100000$，$0 \leq k \leq 1$。

样例

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

8