4380. [郑轻校赛 2026] 和异位

Problem E. 和异位

给定一个 $n$ 个点 $m$ 条边的无向连通图，每条边有一个非负整数权值。定义一条路径的权值为路径上所有边权的异或和（即按位异或运算的结果）。

现有 $q$ 次询问，每次给出两个节点 $s$ 和 $t$，求从 $s$ 到 $t$ 的所有路径中，权值的最小值。

异或运算：对于两个二进制位，相同得 $0$，不同得 $1$。多个数的异或和即为将它们依次进行异或运算得到的结果。

Input

第一行包含两个整数 $n,m$ $(1 \le n \le 10^5,\ n-1 \le m \le 2\times 10^5)$，分别表示点数和边数。

接下来 $m$ 行，每行包含三个整数 $u,v,w$ $(1 \le u,v \le n,\ 0 \le w < 10^{18})$，表示一条连接 $u$ 和 $v$ 的无向边，权值为 $w$。保证图连通且无自环，但可能有重边。

接下来一行包含一个整数 $q$ $(1 \le q \le 10^5)$，表示询问数量。

接下来 $q$ 行，每行包含两个整数 $s,t$ $(1 \le s,t \le n,\ s \ne t)$，表示一次询问。

Output

对于每个询问，输出一个整数，即最小异或值。

Example

样例输入1

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

样例输出1

1
1

样例输入2

6 6
1 2 9
2 3 3
3 4 9
3 6 5
4 5 10
5 6 11
2
1 2
2 3

样例输出2

4
3

Note

样例1：

询问 $1 \rightarrow 3$：路径 $1 \rightarrow 4 \rightarrow 2 \rightarrow 3$ 的异或和为 $6 \oplus 4 \oplus 3 = 1$，不存在更小值。

询问 $2 \rightarrow 4$：路径 $2 \rightarrow 3 \rightarrow 4$ 的异或和为 $3 \oplus 2 = 1$。

样例2：

询问 $1 \rightarrow 2$：存在路径使异或和为 $4$，且最小。

询问 $2 \rightarrow 3$：直接路径异或和为 $3$，最小。

来源

郑州轻工业大学“筑梯杯”第十八届程序设计大赛暨省内高校邀请赛 E

数据来源：qiuyu