20639번 - Cactus 다국어

A cactus graph is a connected undirected graph without self-loops and multiple edges in which each edge belongs to at most one simple cycle.

Given is a cactus graph $G$ with $N$ vertices, numbered from $1$ to $N$, and $M$ edges. The $i$-th edge connects vertices $a_i$ and $b_i$, and its cost is $c_i$.

Let the cost of a simple path on graph $G$ be bitwise XOR of the costs of all the edges on that path.

Answer $Q$ queries of the form "$x_i$ $y_i$ $k_i$}': consider the costs of all simple paths connecting vertices $x_i$ and $y_i$, remove duplicate values, sort the values in ascending order, and take $k_i$-th element. If the number of these values is less than $k_i$, answer $-1$.

The first line of the input contains two integers $N$ and $M$: the number of vertices and the number of edges in the graph ($2 \le N \le 10^5$, $N-1 \le M \le 2 \cdot 10^5$).

Each of the next $M$ lines describes one edge and contains three integers $a_i$, $b_i$ and $c_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $0 \le c_i < 2^{30}$).

Then follows a line containing an integer $Q$: the number of queries ($1 \le q \le 2 \cdot 10^5$).

Each of the next $Q$ lines describes one query and contains three integers $x_i$, $y_i$ and $k_i$ ($1 \le x_i, y_i \le N$, $x_i \ne y_i$, $1 \le k_i \le 2^{30}$).

It is guaranteed that the graph given in the input is a cactus graph.

For each query, print one integer on a separate line: the answer to that query.