AT_abc451_g.[ABC451G] Minimum XOR Walk

$ N $ 頂点 $ M $ 辺からなる単純連結無向グラフが与えられます。 頂点には $ 1 $ から $ N $ までの、辺には $ 1 $ から $ M $ までの番号がそれぞれ付けられており、辺 $ i $ は頂点 $ U_i $ と頂点 $ V_i $ を結ぶ重み $ W_i $ の無向辺です。

$ 2 $ 頂点を結ぶウォークの重みを、そのウォークが含む辺の重みの総 XOR とします。 ただし同じ辺を複数回通る場合、その辺の重みは通った回数分総 XOR に寄与するものとします。

非負整数 $ K $ が与えられます。整数の組 $ (x,y) $ $ (1\leq x\lt y\leq N) $ であって、頂点 $ x,y $ を結ぶウォークの重みの最小値が $ K $ 以下であるものの個数を求めてください。

$ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

ウォークとは無向グラフ $ G $ 上の頂点 $ X,Y $ に対して、 $ k $ 個の頂点と $ k-1 $ 個の辺を交互に並べた列 $ (v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k) $ であって、 $ v_1=X,v_k=Y $ かつ $ i=1,2,\dots,k-1 $ に対して $ e_i $ が $ v_i $ と $ v_{i+1} $ を結ぶ辺であるようなものを頂点 $ X $ から頂点 $ Y $ への ウォーク と呼びます。

XOR とは非負整数 $ A, B $ のビット単位 XOR、 $ A \oplus B $ は、以下のように定義されます。

• $ A \oplus B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。

例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101 = 110 $ )。 一般に $ k $ 個の非負整数 $ p_1, p_2, p_3, \dots, p_k $ のビット単位 XOR は $ (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) $ と定義され、これは $ p_1, p_2, p_3, \dots, p_k $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる。

$ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $

ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。

$ N $ $ M $ $ K $ $ U_1 $ $ V_1 $ $ W_1 $ $ U_2 $ $ V_2 $ $ W_2 $ $ \vdots $ $ U_M $ $ V_M $ $ W_M $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについての答えを出力せよ。

Sample Explanation 1

一つ目のテストケースにおいて、例えば頂点 $ 1,3,2,1,3 $ を順に通るウォークの重みは $ 4 \oplus 2 \oplus 3 \oplus 4 = 1 $ です。

相異なる頂点の組それぞれに対し、それらを結ぶウォークの重みの最小値は以下のようになることが示せます。

• 頂点 $ 1 $ と頂点 $ 2 $ ：最小値 $ 3 $
• 頂点 $ 1 $ と頂点 $ 3 $ ：最小値 $ 1 $
• 頂点 $ 1 $ と頂点 $ 4 $ ：最小値 $ 2 $
• 頂点 $ 2 $ と頂点 $ 3 $ ：最小値 $ 2 $
• 頂点 $ 2 $ と頂点 $ 4 $ ：最小値 $ 1 $
• 頂点 $ 3 $ と頂点 $ 4 $ ：最小値 $ 3 $

このうち最小値が $ K(=2) $ 以下の組は $ 4 $ 組あります。したがって一行目には $ 4 $ を出力してください。

Constraints

• $ 1 \leq T \leq 10^5 $
• $ 2 \leq N \leq 2 \times 10^5 $
• $ N-1 \leq M \leq 2 \times 10^5 $
• $ 0 \leq K \lt 2^{30} $
• $ 1 \leq U_i \lt V_i \leq N $
• $ 0 \leq W_i \lt 2^{30} $
• 与えられるグラフは単純かつ連結
• 入力はすべて整数
• $ 1 $ つの入力に含まれるテストケースについて、 $ N $ の総和は $ 2 \times 10^5 $ 以下
• $ 1 $ つの入力に含まれるテストケースについて、 $ M $ の総和は $ 2 \times 10^5 $ 以下