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^{\prime }$ 满足：

• $E^{\prime }\subseteq E$
• $(V,E^{\prime })$ 满足给出的 $k$ 条限制：第 $i$ 条限制是在 $(V,E^{\prime })$ 上，从 $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 {\displaystyle (\genfrac{}{}{0ex}{}{n}{2})}$，$0\le k\le n(n-1)$，$1\le u\ne v\le n$，$1\le s_i,t_i\le n$，$1\le c_i\le 2$。

时间限制：$\mathtt{\text{4s}}$

空间限制：$\mathtt{\text{1GB}}$