Problem Description

Given a connected undirected edge cactus graph with edge weights, answer multiple queries. For each query, find the minimum possible XOR sum of edge weights along a vertex-simple (no repeated vertices) path between two given nodes.

Note: The original graph may contain multiple edges and self-loops. A cycle formed by a pair of parallel edges is also considered a cycle. Self-loops clearly do not affect this problem.

Input Format

The first line contains three integers $n,m,k$, where $n$ is the number of vertices, $m$ is the number of edges, and $k$ is the number of queries.

The next $m$ lines each contain three integers $l_i,r_i,v_i$, meaning there is an edge between $l_i$ and $r_i$ with weight $v_i$.

The next $k$ lines each contain two integers $l_i,r_i$, meaning: query the minimum XOR value of edge weights over all vertex-simple paths between $l_i$ and $r_i$.

Output Format

Output $k$ lines. Each line contains one integer, the answer to the $i$-th query in order.

4 4 3
1 2 1
2 3 2
3 4 3
4 2 4
1 4
1 3
2 4

0
3
1

Hint

Sample Explanation

The first query: $1\to2\to3\to4,1\bigoplus2\bigoplus3=0$.

The second query: $1\to2\to3,1\bigoplus2=3$.

The third query: $2\bigoplus3=1$.

Constraints

For all testdata, $n\le5\times10^5,k\le10^5,v\le10^9$. The detailed constraints are as follows:

Special Notes

The testdata for this problem is not easy to create, and there are many wrong solutions or solutions with too high time complexity, so it may be quite strict on constant factors. You are welcome to submit hack testdata.

Currently, common wrong solutions that are not guaranteed to be hacked include:

1. Let me see whether $nk\log V$ can pass.
2. I think heavy-light decomposition with $k\log^4$ can pass.
3. I guess long-chain decomposition / binary lifting linear basis with $k\log^3$ can pass.
4. I think $(n\log n)^{\frac{4}{3}}$ tree blocking + linear basis can pass.
5. Various boundary issues, and so on.

Translated by ChatGPT 5