← 返回题目列表

AtCoder · tkppc6_2_l

L. 转到

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

配点 : 800 点

問題文

帕肯王国是 N 镇 1, 2, \ldots, N 和 M 书籍之路 1, 2, \ldots, M 由一条道路组成 i 是一座城市 A_i 和城市 B_i 双向连接。

时间是 2021 2017年,一种新病毒传播到帕肯王国,因此道路被设计成只能朝一个方向通过,以遏制人员流动。 然而,由于我们希望将对经济的影响降至最低,因此定义如下。转到学位 我想让尽可能大。

转到学位 我想让 : 街 u 从城市出发 v 至 0 可以通过多条道路行驶的一组城镇。 (u, v) 的数量

可能的道路方向是 2^M 有多种方法可以做到这一点,但请计算所有这些方法的 GoTo 度并输出最大值。

制約

  • 1 \leq N, M \leq 10^5
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
  • 假设每条道路都可以双向通行,从任何城市到任何城市。 0 可以通过多条道路移动。 最佳方向是
  • 所有输入均为整数

入力

输入将以以下形式从标准输入给出。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答案 请打印除以 1 行输出。 从


入力例 1

3 2
1 2
2 3

出力例 1

6

例如, 1 \rightarrow 2, 2 \rightarrow 3 。

此时, u 到 v 至 0 可以沿着书本的多个侧面移动。 集合 (u,v) 是 (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 的 6 一。 满足


入力例 2

3 3
1 2
1 3
2 3

出力例 2

9

例如, 1 \rightarrow 2, 1 \leftarrow 3, 2 \rightarrow 3 。

此时从任意顶点到任意顶点 0 答案是 3 \times 3 = 9 。


入力例 3

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

出力例 3

27

原案: shiomusubi496