想象一个有 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)}