問題文
KU 大学流行一种独特的拉力赛。 本次比赛的赛道包括N 休息区和 有 M 路径,i 路径是 f_i 第一个休息站和 t_i 个休息区之间。 每条路都有一个检查站 当你通过 i 检查站时,无论你往哪个方向走, p_i 的分数使用 XOR 相加。与异或 添加了。我说了两遍,因为这很重要。
在这个游戏中,你可以多次通过相同的休息区和道路。 即使达到了目标,还可以继续集会,但是 禁止绕过沿途检查站到达其他休息区。 所以,它之所以如此受欢迎,是因为你必须认真思考走什么路线才能获得高分。
这次 有 Q 参与者, 第j 位参与者是 从 a_j 处的休息区开始,到 看来我们要去 b_j 休息区。 作为管理方,我决定提前研究一下每个参与者的最高分。
入力形式
输入按以下格式给出。其余区域编号为 0 索引。 输出
N M Q f_1 t_1 p_1 ... f_M t_M p_M a_1 b_1 ... a_Q b_Q
出力形式
Q 行, 从第j 行是 代表 a_j 个休息站出发 输出到第 b_j 个休息站的路线上获得的最高分数。
制約
- 1 \leq N \leq 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq Q \leq 10^5
- 0 \leq f_i, t_i \lt N, f_i \neq t_i
- 0 \leq p_i \lt 2^{60}
- 0 \leq a_j, b_j \lt N
- 您可以从任何休息站沿着道路到达任何休息站。
- 休憩所 f_i,t_i 至多有一条路径连接两者。
- 所有输入值都是整数。
针对该问题的判断设置了一组60分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- M \leq 20
入出力例
入力例1
5 5 3 0 1 7 1 2 22 2 3 128 3 4 128 4 2 128 0 1 0 0 3 4
出力例1
135 128 128
作者:森悟 测试员:田村一则