AND-MEX Walk
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs

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 < 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.

Input format:
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 < 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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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).

Example input:
6 7
1 2 1
2 3 3
3 1 5
4 5 2
5 6 4
6 4 6
3 4 1
3
1 5
1 2
5 3

Example output:
2
0
1

Example input:
9 8
1 2 5
2 3 11
3 4 10
3 5 10
5 6 2
5 7 1
7 8 5
7 9 5
10
5 7
2 5
7 1
6 4
5 2
7 6
4 1
6 2
4 7
2 8

Example output:
0
0
2
0
0
2
1
0
1
1

Editorial:
Observation: The MEX can only be $$$0$$$, $$$1$$$, or $$$2$$$.
Proof: Suppose the MEX is greater than $$$2$$$. We know that on using the bitwise AND function, some on bits will turn off and the sequence will be non-increasing.
This would imply that we have $$$2$$$, $$$1$$$ and $$$0$$$ in our sequence. However, going from $$$2$$$ (10) to $$$1$$$ (01) is not possible as an off bit gets turned on. Hence, $$$2$$$ and $$$1$$$ can't both be in our sequence.
Case $$$1$$$: MEX is $$$0$$$.
For MEX to be $$$0$$$, there must be a walk from $$$u$$$ to $$$v$$$ such that the bitwise AND of the weights of all the edges in that walk is non-zero. This implies that there exists some bit which is on in all the edges of that walk.
To check this, we can loop over all possible bits, i.e. $$$i$$$ goes from $$$0$$$ to $$$29$$$, and construct a new graph for each bit while only adding the edges which have the $$$i$$$-th bit on. We can use DSU on this new graph and form connected components. This can be processed before taking the queries.
In a query, we can go through all bits from $$$0$$$ to $$$29$$$ and if we get $$$u$$$ and $$$v$$$ in the same component for some bit, then we're done and our answer is $$$0$$$.
Case $$$2$$$: MEX is $$$1$$$.
If we didn't get the MEX to be $$$0$$$, then we know that $$$0$$$ is in our sequence.
Now, in our walk, if we ever get a node which has an even edge (let's say this is the first even edge so far) and our bitwise AND so far is greater than $$$1$$$ (it would also be an odd number since there's no even edges), then including this edge in our walk would guarantee a MEX of $$$1$$$ since the even edge has the $$$0$$$-th bit off. Taking the bitwise AND with this edge guarantees that the last bit stays off until the end of our walk and we never get $$$1$$$ in the sequence. Let us call this node $$$x$$$. For a given $$$u$$$, if an $$$x$$$ exists, then an answer of $$$1$$$ is possible.
This also shows us that the value of $$$v$$$ is not relevant, since after we get the even edge, our MEX is guaranteed to be $$$1$$$ and the subsequent weights do not matter.
For the bitwise AND of the walk to be an odd number greater than $$$1$$$, all edges on the walk from $$$u$$$ to $$$x$$$ must have the $$$0$$$-th bit on and the $$$i$$$-th bit on for some $$$i$$$ in $$$[1, 29]$$$.
Similar to the previous case, we now loop $$$i$$$ from $$$1$$$ to $$$29$$$ and make a new graph for each bit while only adding edges which have the $$$0$$$-th and the $$$i$$$-th bits on, and use DSU to form connected components. Within a component, if any node has an even edge, then every node in that component can be the starting point of a walk to get the answer as $$$1$$$. Then, we go through all the nodes. If the current node, say, $$$y$$$ has an even edge, then we can mark the parent node of $$$y$$$'s component indicating that this component has an even edge.
In the queries, we can go through all the $$$29$$$ graphs and if the parent of $$$u$$$ in a graph has been marked, then we know that it's possible to have the MEX as $$$1$$$.
If not, the answer must be $$$2$$$ since MEX cannot exceed $$$2$$$.
Time complexity: $$$\mathcal{O}(n\log{w}+(m+q)\alpha(n)\log{w})$$$