English Problem Statement

跳蚤国运动会在首都跳蚤利亚举行，来自全国各地的跳蚤居民蜂拥而至。为了确保运动会期间的交通秩序，跳蚤国王决定对首都的道路进行管制。

跳蚤利亚的道路系统可以看作一张由 $n$ 个路口和 $m$ 条双向道路 $(u,v)$ 组成的网络。保证 $u\ne v$，且对于每对路口之间，最多存在一条道路（即没有重边，自环）。

国王需要选择一部分道路保持开放，其余道路暂时封闭。

然而，为了保证观众能顺利抵达赛场并为心仪的战队加油，开放的道路必须满足一系列特殊限制：

对于第 $i$ 个限制，从路口 $s_i$ 到路口 $t_i$，在开放的道路中至少要存在 $c_i$（$1\le c_i\le 2$）条不同的边简单路径。

• 边简单路径的定义是：不经过重复道路的路径，且一条道路不允许从两个方向经过。
• 不同的边简单路径的定义是：经过的路口序列不完全相同的边简单路径。
• 特别地，路径可以只经过一个路口，在 $s_i=t_i$ 时这类路径也应被计入。

你需要帮助跳蚤国王计算出满足所有限制条件的道路开放方案数，答案对 $998244353$ 取模。

形式化题面：

给定一张 $n$ 个点 $m$ 条边的无向图 $G=(V,E)$，求有多少边集 $E'$ 满足：

• $E' \subseteq E$
• $(V,E')$ 满足给出的 $k$ 条限制：第 $i$ 条限制是在 $(V,E')$ 上，从 $s_i$ 到 $t_i$ 必须至少有 $c_i$ 条不同的边简单路径（$1 \le c_i \le 2$）。

答案对 $998244353$ 取模。

输入格式

第一行三个整数 $n,m,k$。分别表示路口数、道路数、限制数量。

接下来 $m$ 行，每行两个整数 $u,v$，描述一条道路 $(u,v)$。保证没有重边、自环。

接下来 $k$ 行，每行三个整数 $s_i,t_i,c_i$，描述一条限制。

输出格式

一行一个整数，表示满足所有限制条件的道路开放方案数对 $998244353$ 取模的结果。

样例零

input

4 6 4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 1
1 1 2
2 3 2
2 4 2

output

19

样例一~七

见下发文件。

数据范围

对于所有数据，保证 $1 \le n \le 16$，$0 \le m \le \dbinom{n}{2}$，$0 \le k \le n(n-1)$，$1 \le u \neq v \le n$，$1 \le s_i,t_i \le n$，$1 \le c_i \le 2$。

时间限制：$\texttt{4s}$

空间限制：$\texttt{1GB}$