単純無向グラフで、任意の辺が高々 $1$ つの単純閉路にしか含まれないようなものをサボテングラフと呼ぶことにします。
$N$ 頂点 $M$ 辺の連結なサボテングラフ $G$ が与えられます。
各頂点は $1$ から $N$ まで番号が付いています。
また、$i$ 個目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでおり、コストは $c_i$ です。
グラフ $G$ 上の単純パスのコストを、そのパス上に含まれる全ての辺のコストの XOR と定めます。
以下のような形式の $Q$ 個のクエリに答えてください。
x_i y_i k_i
― 頂点 $x_i$ と頂点 $y_i$ を繋ぐすべての単純パスのコストを列挙して重複する値を除き、小さい順に並べた列を $d = d_1, d_2, ... , d_L$ としたときに、$d_{k_i}$ を求めよ。ただし、このコスト列 $d$ の長さ $L$ が $k_i$ より小さい場合は $-1$ とする。入力は以下の形式で標準入力から与えられる。
$N$ $M$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $:$ $a_M$ $b_M$ $c_M$ $Q$ $x_1$ $y_1$ $k_1$ $x_2$ $y_2$ $k_2$ $:$ $x_Q$ $y_Q$ $k_Q$
$Q$ 個のクエリの答えを一行ごとに順番に出力せよ。
4 4 1 2 1 1 3 8 3 2 0 1 4 7 4 1 2 1 2 1 2 1 4 1 3 4 1073741824
1 8 7 -1
頂点 $1$ から頂点 $2$ への単純パスは、辺 $1$ のみを経由するものと、辺 $2, 3$ を経由するもので、コストはそれぞれ $1$, $8$ です。なので、$1$ つめのクエリの答えは $1$となります。
頂点 $2$ から頂点 $1$ への単純パスも上記と同様なので、 $2$ つ目のクエリの答えは $8$ となります。
頂点 $1$ から頂点 $4$ への単純パスは、辺 $4$ のみを経由するもののみで、コストは $7$ です。なので、$3$ つ目のクエリの答えは $7$ となります。
頂点 $3$ から頂点 $4$ への単純パスは、辺 $2$, $4$ を経由するものと、辺 $3$, $1$, $4$ を経由するもので、コストはそれぞれ $15$, $6$ です。$1073741824$ 番目に小さいコストは存在しないので、$4$ つ目のクエリの答えは $-1$ となります。
13 15 1 2 1 2 3 2 3 4 3 4 5 1 5 1 2 5 6 4 6 7 15 7 8 9 8 6 7 2 9 5 9 10 5 10 2 2 3 11 3 11 12 2 11 13 1 8 12 13 1 1 11 2 9 5 4 2 7 3 6 12 2 9 7 5 10 3 3 3 12 2
3 3 7 10 7 -1 2 -1