← 返回题目列表

Codeforces · 615/B

B. 长尾刺猬

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

这位圣诞圣诞老人给了玛莎一张神奇的图画和一支铅笔。该图片由由 m 个线段连接的 n 个点组成(它们可能以任何方式交叉,但这并不重要)。没有两条线段连接同一对点,也没有线段将点与其自身连接。玛莎想要给一些片段上色,以便画出一只刺猬。在玛莎的心目中,每只刺猬都由一条尾巴和一些刺组成。她想画出满足以下条件的尾巴:

1.只能对图片上已经呈现的片段进行绘制;
2. 尾部应该是连续的,即由一些点序列组成,使得每两个相邻点由彩色线段连接;
3. 从尾部开始到结束的点数应严格增加。

Masha 将尾巴的长度定义为其中点数。另外,她想画一些刺。为此,玛莎将绘制所有片段,使它们的末端之一成为尾巴的端点。玛莎将刺猬的美丽定义为尾巴的长度乘以刺的数量。玛莎想给最美丽的刺猬上色。帮助她计算她希望得到什么结果。

请注意,根据玛莎对刺猬的定义,一个节段可能同时充当脊柱和尾巴的一部分(她毕竟是一个小女孩)。查看图片以获得进一步的说明。

输入

输入的第一行包含两个整数 n 和 m(2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) – 分别是图片上的点数和段数。

然后是 m 行,每行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi)——相应线段连接的点数。确保没有两个线段连接同一对点。

输出

打印刺猬美丽的最大可能值。

示例

输入 #1

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

输出 #1

9

输入 #2

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

输出 #2

12

注意

下图对应第一个示例。形成刺猬的部分被漆成红色。尾部由一系列编号为 1、2 和 5 的点组成。以下节段是刺:(2, 5)、(3, 5) 和 (4, 5)。因此,刺猬的美丽等于3·3=9。