← 返回题目列表

Codeforces · 1218/D

D. 异或生成树

中文机器翻译题面 查看原题

在遥远的银河系中有一个古老的星际共和国泡泡国,由 $$$N$$$ 个行星组成。它们之间有$$$M$$$双向虫洞,每个虫洞连接一对行星。泡泡之地是一个非常集中的共和国,有一个首都行星白色星球,从那里可以使用这些虫洞到达任何其他星球。还保证没有虫洞将行星与其自身连接,并且没有两个不同的虫洞连接同一对行星。

我们将一条从一颗行星开始,访问其他行星且每个行星最多一次并返回起点的路径称为旅行。星际安全条例保证每个星球最多属于一个旅行团,并且最多有 $$$42$$$ 旅行团。

经过许多亿万年的使用,虫洞需要修复,每个虫洞都有$$$W_{i}$$$的修复费用。不幸的是,泡沫之地参议院预算不足。因此,他们决定只修复所需数量的虫洞,以便让资本可以到达所有行星,并为修复支付尽可能少的钱。然而,参议院计算成本的方式有所不同。一组赔偿的成本是每个单独赔偿的成本的二元异或,也就是说,如果要进行的赔偿成本为 $$$A_{1},A_{2},...,A_{k}$$$,则整个集合的成本为 $$$A_{1} \oplus A_{2} \oplus ... \oplus A_{k}$$$。

现在参议院想知道他们必须支付多少钱,以及实现该成本以 $$$1000000007$$$ 为模的不同方法的数量。

输入

输入的第一行包含两个数字 $$$N (1 \leq N \leq 100.000)$$$,行星数量和 $$$M (1 \leq M \leq 100.041)$$$,虫洞数量。接下来的 $$$M$$$ 行包含三个数字 $$$U、V (1 \leq U \neq V \leq N)$$$ 和 $$$W (1 \leq W \leq 100.000)$$$,意味着存在连接行星 $$$U$$$ 和 $$$V$$$ 的虫洞,修复成本为 $$$W$$$。

输出

输出两个数字,即整个补偿的最小可能成本以及以该成本模 $$$1000000007$$$ 的不同有效补偿的数量。

示例

输入 #1

6 6
4 1 5
5 2 1
6 3 2
1 2 6
1 3 3
2 3 4

输出 #1

1 1

注意

我们可以修复虫洞 $$$1$$$,$$$2$$$,$$$3$$$,$$$5$$$ 和 $$$6$$$,支付 $$$5 \oplus 1\oplus 2 \oplus 3 \oplus 4=1$$$,可以检查这是所有行星都连接起来的最便宜的修复,也是唯一有效的修复。