[Solution] AND-MEX Walk solution codeforces

AND-MEX Walk solution codeforces – 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 𝑝1,𝑝2,,𝑝𝑘p1,p2,…,pk (which are not necessarily distinct) starting with 𝑢u and ending with 𝑣v, such that 𝑝𝑖pi and 𝑝𝑖+1pi+1 are connected by an edge for 1𝑖<𝑘1≤i<k.

[Solution] AND-MEX Walk solution codeforces

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 [𝑤1,𝑤2,,𝑤𝑘1][w1,w2,…,wk−1] where 𝑤𝑖wi is the weight of the edge between 𝑝𝑖pi and 𝑝𝑖+1pi+1. Then the length of the walk is given by MEX({𝑤1,𝑤1&𝑤2,,𝑤1&𝑤2&&𝑤𝑘1})MEX({w1,w1&w2,…,w1&w2&…&wk−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}{2,1} is 00, because 00 does not belong to the set.
  • The MEX of {3,1,0}{3,1,0} is 22, because 00 and 11 belong to the set, but 22 does not.
  • The MEX of {0,3,1,2}{0,3,1,2} is 44 because 001122 and 33 belong to the set, but 44 does not.

[Solution] AND-MEX Walk solution codeforces

The first line contains two integers 𝑛n and 𝑚m (2𝑛1052≤n≤105𝑛1𝑚min(𝑛(𝑛1)2,105)n−1≤m≤min(n(n−1)2,105)).

Each of the next 𝑚m lines contains three integers 𝑎a𝑏b, and 𝑤w (1𝑎,𝑏𝑛1≤a,b≤n𝑎𝑏a≠b0𝑤<2300≤w<230) 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𝑞1051≤q≤105).

Each of the next 𝑞q lines contains two integers 𝑢u and 𝑣v (1𝑢,𝑣𝑛1≤u,v≤n𝑢𝑣u≠v), the description of each query.

Output

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

Examples
input

Copy
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

[Solution] AND-MEX Walk solution codeforces

output

Copy
2
0
1
input

Copy
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
output

Copy
0
0
2
0
0
2
1
0
1
1

AND-MEX Walk solution codeforces

The following is an explanation of the first example.

AND-MEX Walk solution codeforcesThe graph in the first example.
Here is one possible walk for the first query:

1533211531425.1→53→32→11→53→14→25.

The array of weights is 𝑤=[5,3,1,5,1,2]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}{5,1,0}. The MEX of this set is 22. We cannot get a walk with a smaller length (as defined in the statement).

For Solution

Click here

Leave a Comment