#P1659E. AND-MEX Walk

    ID: 3539 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>bitmasksbrute forcedata structuresdfs and similardsugraphsgreedy

AND-MEX Walk

Description

There is an undirected, connected graph with nn vertices and mm weighted edges. A walk from vertex uu to vertex vv is defined as a sequence of vertices p1,p2,,pkp_1,p_2,\ldots,p_k (which are not necessarily distinct) starting with uu and ending with vv, such that pip_i and pi+1p_{i+1} are connected by an edge for 1i<k1 \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 [w1,w2,,wk1][w_1,w_2,\ldots,w_{k-1}] where wiw_i is the weight of the edge between pip_i and pi+1p_{i+1}. Then the length of the walk is given by MEX({w1,w1&w2,,w1&w2&&wk1})\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 qq queries of the form u v. For each query, find the minimum possible length of a walk from uu to vv.

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 00, 11, 22 and 33 belong to the set, but 44 does not.

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

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

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

Each of the next qq lines contains two integers uu and vv (1u,vn1 \leq u, v \leq n, uvu \neq v), the description of each query.

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

Input

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

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

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

Each of the next qq lines contains two integers uu and vv (1u,vn1 \leq u, v \leq n, uvu \neq v), the description of each query.

Output

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

Samples

样例输入 1

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

样例输出 1

2
0
1

样例输入 2

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

样例输出 2

0
0
2
0
0
2
1
0
1
1

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:

1533211531425.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]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).