← 返回题目列表

AtCoder · abc447_e

E. 除法图

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

分数: 475 点

问题陈述

给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。 在这里, N \geq 2。 顶点已编号 1 to N,并且边缘已编号 1 to M;边缘 i 连接顶点 U_i 和 V_i。 每条边都有一个值,称为 成本 二进制字符串的,以及边缘成本 i is 2^i.

现在您将选择 G 删除,使连通分量的数量 G 正好变成 2。 (可以证明,在本问题的约束下,这总是可以实现的。)

求已删除边的最小可能成本总和,模 998244353。 (请注意,您没有最小化余数模 998244353.)

约束

  • 2 \leq N \leq 2\times 10^5
  • N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)
  • 1 \leq U_i < V_i \leq N
  • (U_i, V_i) \neq (U_j, V_j) if i \neq j
  • G 已连接。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

输出

输出已删除边的最小可能成本总和,模 998244353.


示例输入 1

5 7
2 3
1 2
1 5
4 5
2 4
3 5
1 3

示例输出 1

22

删除边 1, 2, 4 (上图中虚线所示的边)使得连通分量的数量 G 正是 2.

在这种情况下,删除的边的成本总和为 2^1+2^2+2^4=22,这是最小值。


示例输入 2

2 1
1 2

示例输出 2

2

示例输入 3

8 16
2 7
5 7
6 8
1 7
4 7
1 3
2 8
5 8
4 8
2 5
3 4
3 8
1 4
1 8
4 6
1 2

示例输出 3

54