UOJ Logo Universal Online Judge

UOJ

#962. 【UR #30】交通管制

附件下载 统计

English Problem Statement

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

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

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

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

对于第 i 个限制,从路口 si 到路口 ti,在开放的道路中至少要存在 ci1ci2)条不同的边简单路径。

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

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

形式化题面:

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

  • EE
  • (V,E) 满足给出的 k 条限制:第 i 条限制是在 (V,E) 上,从 siti 必须至少有 ci 条不同的边简单路径(1ci2)。

答案对 998244353 取模。

输入格式

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

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

接下来 k 行,每行三个整数 si,ti,ci,描述一条限制。

输出格式

一行一个整数,表示满足所有限制条件的道路开放方案数对 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

样例一~七

见下发文件。

数据范围

对于所有数据,保证 1n160m(n2)0kn(n1)1uvn1si,tin1ci2

子任务编号 分值 n 特殊性质
1 10 7
2 10 16 ci=1
3 30 10
4 10 12
5 10 14
6 15 15
7 15 16

时间限制:4s

空间限制:1GB