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.

제한

힌트