P15426 Time to Heal

:::epigraph[——《Time to Heal》] _时间偷走了记忆_ _I wanna take time to heal_ _承诺是我的底气_ _Even if it took so many_ _问题不去规避_ _现在不再嘴硬_ _我要故事继续书写 maybe_ ::: 我们所深知的，是停留无法结束痛楚，是时间无法治愈感触，是肉体无法抵御孤独。

本题总时限较大，请勿卡评测。我们推荐您在提交本题前先通过本题的 $20$ 个样例。具体见【说明/提示】。 ----------- 我们定义长度为 $l$ 的序列 $\{a_l\}$ 是一个路径当且仅当： - $\forall 1\le i

第一行两个整数 $c$，表示测试点所在子任务编号。对于样例均有 $c=0$。 第二行两个整数 $n,m$。分别表示无向图的点数、边数。 接下来 $m$ 行每行两个整数 $u,v$ 描述无向边。保证输入的是一张简单无向图，注意**图不一定连通**。 接下来一行一个整数 $q$。 之后 $q$ 行，每行三个整数 $S,T,k$ 表示一个询问。

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

### 样例 #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）与题面中提供的相同。 为避免卡评测并方便你的调试，你可以在[这里](https://www.luogu.com.cn/contest/311003)测试本题的 $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 | ### 后记 我们所相信的，是答案要等到最后，是陪伴能打败诅咒，是懂得承担才是最大的成就。