题目描述

徐老师最近又又又在出题了！

这天他需要生成一棵二叉树，这棵二叉树有 $n$ 个节点，其中节点编号 $1 \sim n$，没有属性

但是这棵树的每条边是存在边权的，边权只会从 $0/1$ 中随机生成

徐老师简化了自己题目的题意：对于生成树的要求如下：

给定 $m$ 个条件，每个条件包含三个信息 $u,v,op$

1. 若 $op = 0$ 则表示从 $u$ 到 $v$ 的路径边权之和必须为偶数
2. 若 $op = 1$ 则表示从 $u$ 到 $v$ 的路径边权之和必须为奇数

现在徐老师想知道，一共有多少种不同的满足条件的所有条件的生成树？

由于答案可能很大，请你将答案对 $998244353$ 取模后输出

输入格式

输入第一行包含两个整数 $n,m$ ，含义如题

接下来 $n - 1$ 行，每行包含两个整数 $u,v$ 表示一条树边，连接了 $u,v$ 两个节点

接下去 $m$ 行，每行包含三个整数 $u,v,op$，表示一个条件，含义如题

输出格式

输出一个整数表示有多少种不同的生成树

数据范围

样例输入1

3 0
1 2
2 3

样例输出1

4

样例解释1

没有任何限制，一共两条边，边权任意，则答案为 $2 * 2 = 4$

样例输入2

3 2
1 2
1 3
1 2 0
1 3 0

样例输出2

1

样例解释1

只存在一种情况，两条边的边权均为 $0$ 才满足所有条件

样例输入3

3 1
1 2
2 3
1 2 1

样例输出3

2

样例解释1

只需要满足 $1-2$ 这条边的权值为 $1$，$2-3$ 这条边的权值任意，则答案为 $2$