CF1659E.AND-MEX Walk

There is an undirected, connected graph with $n$ vertices and $m$ weighted edges. A walk from vertex $u$ to vertex $v$ is defined as a sequence of vertices $p_1,p_2,\ldots,p_k$ (which are not necessarily distinct) starting with $u$ and ending with $v$, such that $p_i$ and $p_{i+1}$ are connected by an edge for $1 \leq i \lt k$.

We define the length of a walk as follows: take the ordered sequence of edges and write down the weights on each of them in an array. Now, write down the bitwise AND of every nonempty prefix of this array. The length of the walk is the MEX of all these values.

More formally, let us have $[w_1,w_2,\ldots,w_{k-1}]$ where $w_i$ is the weight of the edge between $p_i$ and $p_{i+1}$. Then the length of the walk is given by $\mathrm{MEX}({w_1,\,w_1\& w_2,\,\ldots,\,w_1\& w_2\& \ldots\& w_{k-1}})$, where $\&$ denotes the bitwise AND operation.

Now you must process $q$ queries of the form u v. For each query, find the minimum possible length of a walk from $u$ to $v$.

The MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set. For instance:

• The MEX of ${2,1}$ is $0$, because $0$ does not belong to the set.
• The MEX of ${3,1,0}$ is $2$, because $0$ and $1$ belong to the set, but $2$ does not.
• The MEX of ${0,3,1,2}$ is $4$ because $0$, $1$, $2$ and $3$ belong to the set, but $4$ does not.

给定一个包含 $n$ 个顶点和 $m$ 条带权无向边的连通无向图。从顶点 $u$ 到顶点 $v$ 的一条**路径（walk）**定义为一个顶点序列 $p_1,p_2,\ldots,p_k$（其中顶点可重复），满足 $p_1 = u$、$p_k = v$，且对每个 $1 \leq i < k$，顶点 $p_i$ 与 $p_{i+1}$ 之间存在一条边。

我们按如下方式定义一条路径的长度：取该路径上边的有序序列，并将每条边的权重依次写入一个数组。接着，计算该数组每个非空前缀的按位与（bitwise AND）值，并将所有这些值构成一个集合。该路径的长度即为此集合的 MEX（最小未出现非负整数）。

更形式化地，设 $[w_1,w_2,\ldots,w_{k-1}]$ 为路径中各边的权重序列，其中 $w_i$ 表示连接 $p_i$ 与 $p_{i+1}$ 的边的权重。则该路径的长度为

$$\mathrm{MEX}\big(\{w_1,\,w_1\& w_2,\,\ldots,\,w_1\& w_2\& \ldots\& w_{k-1}\}\big),$$

其中 $\&$ 表示按位与运算。

现在你需要处理 $q$ 个形如 u v 的查询。对每个查询，求出从 $u$ 到 $v$ 的所有路径中可能的最小长度。

集合的 MEX（minimum excluded value，最小未出现值）是指不属于该集合的最小非负整数。例如：

• 集合 $\{2,1\}$ 的 MEX 是 $0$，因为 $0$ 不在集合中。
• 集合 $\{3,1,0\}$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在集合中，但 $2$ 不在。
• 集合 $\{0,3,1,2\}$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 均在集合中，但 $4$ 不在。

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$; $n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2},10^5\right)}$).

Each of the next $m$ lines contains three integers $a$, $b$, and $w$ ($1 \leq a, b \leq n$, $a \neq b$; $0 \leq w \lt 2^{30}$) indicating an undirected edge between vertex $a$ and vertex $b$ with weight $w$. The input will not contain self-loops or duplicate edges, and the provided graph will be connected.

The next line contains a single integer $q$ ($1 \leq q \leq 10^5$).

Each of the next $q$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$), the description of each query.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$；$n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2},10^5\right)}$）。

接下来的 $m$ 行每行包含三个整数 $a$、$b$ 和 $w$（$1 \leq a, b \leq n$，$a \neq b$；$0 \leq w \lt 2^{30}$），表示一条连接顶点 $a$ 与顶点 $b$ 的无向边，其权重为 $w$。输入中不包含自环或重边，且所给图是连通的。

下一行包含一个整数 $q$（$1 \leq q \leq 10^5$）。

接下来的 $q$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示每个查询。

For each query, print one line containing a single integer — the answer to the query.

对于每个查询，输出一行，包含一个整数——该查询的答案。

The following is an explanation of the first example.

The graph in the first example.

Here is one possible walk for the first query:

$$1 \\overset{5}{\\rightarrow} 3 \\overset{3}{\\rightarrow} 2 \\overset{1}{\\rightarrow} 1 \\overset{5}{\\rightarrow} 3 \\overset{1}{\\rightarrow} 4 \\overset{2}{\\rightarrow} 5.$$

The array of weights is $w=[5,3,1,5,1,2]$. Now if we take the bitwise AND of every prefix of this array, we get the set ${5,1,0}$. The MEX of this set is $2$. We cannot get a walk with a smaller length (as defined in the statement).

以下是第一个样例的说明。

第一个样例中的图。

以下是第一个查询的一种可能的行走路径：

$$1 \\overset{5}{\\rightarrow} 3 \\overset{3}{\\rightarrow} 2 \\overset{1}{\\rightarrow} 1 \\overset{5}{\\rightarrow} 3 \\overset{1}{\\rightarrow} 4 \\overset{2}{\\rightarrow} 5.$$

权重数组为 $w=[5,3,1,5,1,2]$。现在，若对这个数组的每个前缀取按位与（bitwise AND），得到的集合为 ${5,1,0}$。该集合的 MEX 为 $2$。我们无法找到一条满足题面定义的更短的行走路径。