UOJ Logo Universal Online Judge

UOJ

#742. 【ZJOI2022】简单题

附件下载 统计

九条可怜是一个喜欢出简单题的女孩子。顾名思义,简单题就是题目里面出现了很多“简单”。

可怜首先给出一张简单连通无向图,每条边有一个正整数边权。特别地,可怜保证图上任意两个简单环的边权和相等。

后来可怜想要隐藏图里美好的性质,她将其中一部分边的权值改成了新的权值。因此,修改之后原本美好的性质可能就不存在了。

现在她给出修改后的图,同时给出多组询问,每次询问两点 $S, T$ 间所有简单路径权值和。

因为答案可能很大,你只需要输出答案对 $998\,244\,353$ 取模的结果。

具体地,简单图指不存在重边和自环,简单环和简单路径指不包含重复节点。

输入格式

第一行读入三个整数 $n, m, q$。

接下来 $m$ 行,每行三个整数 $u, v, w$,代表一条权值为 $w$ 的无向边 $(u, v)$。

接下来 $q$ 行,读入 $q$ 组询问,每组询问读入一行两个整数 $S, T$。

输出格式

对于每个询问,输出一行一个整数代表答案对 $998\,244\,353$ 取模后的结果。

样例一

input

5 5 6
1 2 10
2 3 2
2 4 5
2 5 4
4 5 3
1 5
2 5
3 5
3 4
4 5
4 4

output

32
12
16
16
12
0

样例二

见附加文件。

限制与约定

对于所有测试点,满足 $1 \le n, q \le 500\,000$,$n - 1 \le m \le 640,000$,$1 \le u, v, S, T \le n$,$1 \le w \le {10}^6$,无重边自环,图连通。

每个测试点的具体限制见下表:

测试点编号 特殊限制 1 特殊限制 2
$1$ $m < n$ 保证存在经过所有点的简单路径
$2$ $m < n$
$3 \sim 5$ 任意一个点不在 $\ge 2$ 个简单环上 保证存在经过所有点的简单路径
$6 \sim 8$ 任意一个点不在 $\ge 2$ 个简单环上
$9 \sim 14$ 保证存在经过所有点的简单路径
$15 \sim 20$

时间限制:$6\texttt{s}$

空间限制:$1024\texttt{MB}$