说明

本题总时限较大，请勿卡评测。我们推荐您在提交本题前先通过本题的 $20$ 个样例。具体见【说明/提示】。

我们定义长度为 $l$ 的序列 $\{a_l\}$ 是一个路径当且仅当：

• $\forall 1\le i<l$，编号为 $a_i$ 与编号为 $a_{i+1}$ 的点在图上有边直接相连。

我们认为它的起点是 $a_1$，终点是 $a_l$。

我们定义一个无序路径对 $(\{a_p\},\{b_q\})$ 的一个 $k$-TS 为：

• 它是一个 $(\{a_p\},\{b_q\})$ 的长度为 $k$ 的公共子序列。
• 它不是任何一个 $(\{a_p\},\{b_q\})$ 的公共子序列的真子序列。

两个子序列 $a,b$ 不同，当且仅当这两个子序列长度不同，或存在一个 $i$ 使得 $a_i\ne b_i$。

显然，一个路径对可能有多个 $k$-TS。

给定一个 $n$ 个点 $m$ 条边的简单无向图，不保证连通，你需要解决 $q$ 次询问：

• 给出三个整数 $S,T,k$，保证 $S\ne T$。你需要求出：对于这对 $S,T$，所有起点为 $S$，终点为 $T$ 的路径任意两两组合（可以组合完全相同的两条路径）产生的所有无序路径对，所产生的所有 $k$-TS 中字典序最小的。无解输出 $-1$。

你只需输出答案 $k$-TS 的所有项的和。

输入格式

第一行两个整数 $c$，表示测试点所在子任务编号。对于样例均有 $c=0$。

第二行两个整数 $n,m$。分别表示无向图的点数、边数。

接下来 $m$ 行每行两个整数 $u,v$ 描述无向边。保证输入的是一张简单无向图，注意图不一定连通。

接下来一行一个整数 $q$。

之后 $q$ 行，每行三个整数 $S,T,k$ 表示一个询问。

输出格式

对于每个询问，输出 $-1$ 表示不存在可能的 $k$-TS，否则输出最小字典序的 $k$-TS 的所有项的和。

0
10 7
7 5
10 2
10 7
9 10
9 7
5 1
4 10
5
8 2 3
10 5 7
4 9 7
5 10 6
9 7 8

-1
46
47
33
40

0
10 18
2 8
2 9
5 2
9 3
9 1
1 4
8 9
4 2
4 9
9 6
7 5
4 7
8 1
9 5
3 4
3 5
8 5
10 8
10
9 6 5
10 6 1
2 1 5
3 6 5
9 7 7
9 5 2
4 2 7
9 3 1
2 9 1
10 7 3

26
-1
6
20
21
14
11
-1
-1
25

0
10 13
5 4
3 8
2 7
7 10
10 5
6 8
1 6
2 8
9 10
4 9
2 3
3 7
5 6
10
3 10 4
7 9 4
3 2 3
3 4 1
1 8 1
6 2 2
8 2 3
1 2 4
7 5 2
4 9 1

17
20
7
-1
-1
8
12
11
12
-1

见附件中的 ttheal_samples.zip

见附件中的 ttheal_samples.zip

提示

样例 #1 解释

对于第一组询问，不存在任何路径 $\{a_p\}$ 使得 $a_1=8,a_p=2$，因此也不存在满足条件的 $3$-TS。

对于第二组询问，取两条路径 $\{a_7\}=\{b_7\}=[10,2,10,2,10,7,5]$ 时，它们唯一的 $7$-TS $[10,2,10,2,10,7,5]$ 的所有项之和 $46$ 即为答案。可以证明，这是所有满足 $a_1=10,a_p=5$ 的路径任意两两组合产生所有的 $7$-TS 中字典序最小的。

对于第四组询问，取路径 $\{a_7\}=[5,1,5,1,5,7,10],\{b_7\}=[5,1,5,7,5,7,10]$，则它们的公共子序列 $[5,1,5,5,7,10]$ 显然是一个 $6$-TS。可以证明，这是所有满足 $a_1=5,a_p=10$ 的路径 $\{a_p\}$ 任意两两组合产生的所有路径对产生的 $6$-TS 中字典序最小的。所以它的所有项之和 $33$ 是答案。

对于第五组询问，答案 $8$-TS 为 $[9,7,5,1,5,1,5,7]$。请注意我们允许路径 $\{a_p\}$ 中存在 $i\ne p$ 使得 $a_i=a_p$。

样例 #4 至 #20 解释

为了方便你的调试，我们在本题的附件中提供了本题的完整样例文件，共有 $20$ 个，其中前三个（样例 #1 至 #3）与题面中提供的相同。

为避免卡评测并方便你的调试，你可以在这里测试本题的 $20$ 个样例而不在本题的完整数据上测试，比赛邀请码为 bd8m。该比赛中样例测试题目的题目描述中包括了每个样例的具体范围。

这些样例，无疑是善良的出题人无私的馈赠。出题人相信，这些美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

数据范围

对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$0\le m\le 5\times 10^5$，$1\le q\le2\times 10^5$，$1\le k\le 10^9$，$1\le S,T\le n$。特别地，$S\ne T$。保证输入的是一个简单无向图。

::cute-table{tuack} | 子任务 | $n,m,q\le$ | $k\le$ | 特殊性质 | 得分 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 0 | 无特殊限制 | $10^9$ | 本题下发文件中的 $20$ 个样例 | $0$ | 无 | | 1 | $4$ | $6$ | 无 | $5$ | 无 | | 2 | $8$ | $7$ | 无 | $10$ | 1 | | 3 | $300$ | $300$ | 无 | $10$ | 1, 2 | | 4 | $3\times 10^3$ | $3\times 10^3$ | 无 | $15$ | 1, 2, 3 | | 5 | $2\times 10^5$ | $10^9$ | $k\ge 2n$ | $15$ | 无 | | 6 | $2\times 10^5$ | $10^9$ | 保证图是一个森林 | $15$ | 无 | | 7 | $2\times 10^5$ | $10^9$ | 图中没有度数小于 $2$ 的点 | $15$ | 无 | | 8 | $2\times 10^5$ | $10^9$ | 无 | $10$ | 1 至 7| | 9 | 无特殊限制 | $10^9$ | 无 | $5$ | 0 至 8 |

后记

我们所相信的，是答案要等到最后，是陪伴能打败诅咒，是懂得承担才是最大的成就。