← 返回题目列表

Codeforces · 475/E

E. 紧密联系的城市 2

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

想象一个有 n 个路口和 m 条街道的城市。结点从 1 到 n 编号。

为了增加交通流量,市长决定将每条街道改为单向。这意味着在交叉路口 u 和 v 之间的街道上,交通仅从 u 流向 v 或仅从 v 流向 u。

问题是以最大化 (u, v) 数量(其中 1 ≤ u, v ≤ n)的方式引导街道交通流,并且可以通过沿指定方向穿过街道从 u 到达交叉点 v。您的任务是找出此类对的最大可能数量。

输入

输入的第一行包含整数n和m,($$1 \leq n \leq 2000, n - 1 \leq m \leq \frac{n(n-1)}{2}$$),表示城市的路口和街道的数量。

以下 m 行每行包含两个整数 u 和 v,(u ≠ v),表示城市中街道的端点。

每两个路口之间最多有一条街道。可以保证在市长决定之前(当所有街道都是双向的时),可以从任何其他路口到达每个路口。

输出

打印 (u, v) 的最大数量,以便在引导街道后可以从 u 到达交叉点 v。

示例

输入 #1

5 4
1 2
1 3
1 4
1 5

输出 #1

13

输入 #2

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

输出 #2

16

输入 #3

2 1
1 2

输出 #3

3

输入#4

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

输出#4

27

注意

在第一个示例中,如果市长将第一条和第二条街道设置为单向通往交叉路口 1,将第三条和第四条街道设置为相反方向,则将有 13 对可到达的交叉路口:{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}