XOR Path in Graph with Zero-Cycle Property

Given a simple undirected connected graph \(G\) with \(n\) vertices and \(m\) edges. Each edge has an associated weight. The graph does not contain any self-loops or multiple edges.

Define the weight of a simple path as the XOR sum of all edge weights along the path:

\[ w(P)=w_{e_1}\oplus w_{e_2}\oplus\cdots\oplus w_{e_k} \]

It is guaranteed that every simple cycle in \(G\) has an overall XOR sum equal to \(0\). This implies that for any two vertices \(x\) and \(y\), all simple paths between them yield the same XOR sum.

There are \(Q\) queries, each asking for the XOR sum along the simple path from vertex \(x\) to vertex \(y\>.

Note: Since every cycle has an XOR sum of \(0\), one can assign each vertex a value \(f[v]\) such that for any edge \((u,v)\) with weight \(w\), \(f[u]\oplus f[v]=w\). Thus, the answer to each query is \(f[x]\oplus f[y]\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le 10^5,\, 1 \le m \le 10^5)\), representing the number of vertices and edges, respectively. The following \(m\) lines each contain three integers \(u\), \(v\), and \(w\) \((0 \le w \le 10^9)\) indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\).

The next line contains an integer \(Q\) \((1 \le Q \le 10^5)\), denoting the number of queries. Each of the following \(Q\) lines contains two integers \(x\) and \(y\), representing a query asking for the XOR sum along the simple path from \(x\) to \(y\>.

outputFormat

For each query, output a single integer — the XOR sum along the simple path from \(x\) to \(y\).

sample

3 2
1 2 3
2 3 5
2
1 3
2 3

6
5

</p>