跳蚤国运动会在首都跳蚤利亚举行,来自全国各地的跳蚤居民蜂拥而至。为了确保运动会期间的交通秩序,跳蚤国王决定对首都的道路进行管制。
跳蚤利亚的道路系统可以看作一张由 $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$。
子任务编号 | 分值 | $n\le$ | 特殊性质 |
---|---|---|---|
$1$ | $10$ | $7$ | 无 |
$2$ | $10$ | $16$ | $c_i=1$ |
$3$ | $30$ | $10$ | 无 |
$4$ | $10$ | $12$ | 无 |
$5$ | $10$ | $14$ | 无 |
$6$ | $15$ | $15$ | 无 |
$7$ | $15$ | $16$ | 无 |
时间限制:$\texttt{4s}$
空间限制:$\texttt{1GB}$