Longtail Hedgehog

题意翻译

在暑假里，沙耶非常喜欢画画。某一天，爷爷给她一幅画和一支笔。这幅画有n个点和m条线（这些线有可能会相交，不过我们可以先不理它）。每条线的左右两端是两个不一样的点，没有任何两条不同的线的两个端点是完全一样的。现在，沙耶想要给画中的一些线条涂上颜色，沙耶想要的是画出一只刺猬出来。在沙耶的印象中，刺猬应该有一个尾巴和若干根刺。她觉得画尾巴的时候应该满足如下规律： - 1、只能够给画中有的线条涂上颜色。 - 2、尾巴应该是一条连续的包含若干个点的长线，每两个点之间的线条会被涂上了颜色。 - 3、尾巴上的点的序号应该要按顺序严格递增。 沙耶觉得尾巴的长度就是尾巴上的点的个数。同时，沙耶也要画出刺猬的刺，因此她把一些线条也涂上了颜色，刺的一个端点必须和尾巴的末端点一样。沙耶觉得刺猬的美观值应该是尾巴的长度乘以刺的数量。沙耶想要画出一只美观值最大的刺猬。虽然大家觉得沙耶的想法很幼稚，但是她毕竟还是一个小萝莉。。。 ## 输入 输入第一行包含两个正整数n和m，分别表示点和线的数量。(2<=n<=100000,1<=m<=200000)。 接下来m行，每行两个正整数ui和vi，表示第i条线两端的点的序号,1<= ui,vi<= n。数据保证没有两条线的两个端点完全一样。 ## 输出 输出最大的美观值

题目描述

This Christmas Santa gave Masha a magic picture and a pencil. The picture consists of $ n $ points connected by $ m $ segments (they might cross in any way, that doesn't matter). No two segments connect the same pair of points, and no segment connects the point to itself. Masha wants to color some segments in order paint a hedgehog. In Mashas mind every hedgehog consists of a tail and some spines. She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted; 2. The tail should be continuous, i.e. consists of some sequence of points, such that every two neighbouring points are connected by a colored segment; 3. The numbers of points from the beginning of the tail to the end should strictly increase. Masha defines the length of the tail as the number of points in it. Also, she wants to paint some spines. To do so, Masha will paint all the segments, such that one of their ends is the endpoint of the tail. Masha defines the beauty of a hedgehog as the length of the tail multiplied by the number of spines. Masha wants to color the most beautiful hedgehog. Help her calculate what result she may hope to get. Note that according to Masha's definition of a hedgehog, one segment may simultaneously serve as a spine and a part of the tail (she is a little girl after all). Take a look at the picture for further clarifications.

输入输出格式

输入格式

First line of the input contains two integers $ n $ and $ m $ ( $ 2<=n<=100000 $ , $ 1<=m<=200000 $ ) — the number of points and the number segments on the picture respectively. Then follow $ m $ lines, each containing two integers $ u_{i} $ and $ v_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ u_{i}≠v_{i} $ ) — the numbers of points connected by corresponding segment. It's guaranteed that no two segments connect the same pair of points.

输出格式

Print the maximum possible value of the hedgehog's beauty.

输入输出样例

输入样例 #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

说明

The picture below corresponds to the first sample. Segments that form the hedgehog are painted red. The tail consists of a sequence of points with numbers $ 1 $ , $ 2 $ and $ 5 $ . The following segments are spines: ( $ 2 $ , $ 5 $ ), ( $ 3 $ , $ 5 $ ) and ( $ 4 $ , $ 5 $ ). Therefore, the beauty of the hedgehog is equal to $ 3·3=9 $ .