Description

Given a simple, undirected, connected graph $G$ with $n$ vertices and $m$ edges. Each edge has a weight. It is guaranteed that there are no multiple edges and no self-loops.

Define the weight of a simple path as the XOR sum of the weights of all edges on the path.

It is guaranteed that there is no simple cycle in $G$ whose edge-weight XOR sum is not $0$.

There are $Q$ queries asking for the shortest simple path from $x$ to $y$.

Input Format

The first line contains three positive integers $n, m, Q$.

The next $m$ lines each contain three non-negative integers $x, y, v$ ($1 \le x, y \le n$), representing an undirected edge connecting $x$ and $y$ with weight $v$. It is guaranteed that there are no multiple edges and no self-loops.

The next $Q$ lines each contain two positive integers $x, y$ ($1 \le x, y \le n$), representing a query.

Output Format

Output $Q$ lines, each containing one integer as the answer.

3 2 1
1 2 2
2 3 3
1 3

1

Hint

For $100\%$ of the testdata, $1 \le n \le {10}^5$, $1 \le m \le 2n$, and $0 \le v < 2^{30}$.

Translated by ChatGPT 5