CF1218D Xor Spanning Tree

在遥远的银河系中，有一个古老的星际共和国 Bubbleland，由 $N$ 个行星组成。它们之间有 $M$ 条双向虫洞，每条虫洞连接一对行星。Bubbleland 是一个高度集中的共和国，拥有一个首都行星 Whiteplanet，从首都可以通过这些虫洞到达任何其他行星。保证没有虫洞连接自身，也没有两条不同的虫洞连接同一对行星。 我们称一条从某个行星出发，访问其他行星且每个行星最多访问一次，最后回到起点的路径为一次巡游。星际安全条例保证每个行星最多属于一次巡游，并且最多有 $42$ 次巡游。 经过无数年代的使用，虫洞需要修复，每条虫洞的修复费用为 $W_{i}$。不幸的是，Bubbleland 的参议院预算紧张。因此，他们决定只修复必要的虫洞，以保证所有行星都能从首都到达，并且修复费用尽可能少。然而，参议院计算费用的方式不同。修复费用集合的总费用是每条虫洞修复费用的二进制异或和。也就是说，如果修复的虫洞费用为 $A_{1},A_{2},...,A_{k}$，则总费用为 $A_{1} \oplus A_{2} \oplus ... \oplus A_{k}$。 现在，参议院想知道他们最少需要支付多少费用，以及有多少种不同的修复方案可以达到这个费用，答案对 $1000000007$ 取模。

输入的第一行包含两个整数 $N$（$1 \leq N \leq 100000$），表示行星数，以及 $M$（$1 \leq M \leq 100041$），表示虫洞数。接下来的 $M$ 行，每行包含三个整数 $U, V$（$1 \leq U \neq V \leq N$）和 $W$（$1 \leq W \leq 100000$），表示存在一条连接行星 $U$ 和 $V$ 的虫洞，修复费用为 $W$。

输出两个整数，分别表示最小可能的总修复费用，以及达到该费用的不同有效修复方案数，对 $1000000007$ 取模。

我们可以修复虫洞 $1$、$2$、$3$、$5$ 和 $6$，支付的费用为 $5 \oplus 1 \oplus 2 \oplus 3 \oplus 4 = 1$，可以验证这是所有行星连通且费用最小的修复方案，并且只有这一种方案达到该费用。 由 ChatGPT 4.1 翻译