You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

游览计划(tour)

题目描述

小 B 写大模拟题写烦了，于是来到了一个旅游景点散散心。

这个旅游景点的地图共有 $n$ 处地点，在这些地点之间连有 $m$ 条双向道路。旅客从一个景点前往另一个景点需要乘坐景点提供的旅游大巴，旅游大巴会按照经过道路条数最少的路线行驶。

小 B 购买的景区套票让小 B 只能游览这 $n$ 处地点中的 $4$ 处，而且小 B 喜欢浏览沿途的风景，所以小 B 希望选出这 $4$ 处不同的景点 $a,b,c,d$，使 $a\to b,b\to c,c\to d$ 这三条旅游大巴行驶路线经过的道路数量总和最多。

你只需要输出最多的道路数量是多少。

输入格式

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 条道路连接了第 $x_i$ 和 $y_i$ 处地点。

输出格式

共一行一个整数，表示答案。

样例一

输入

6 10
1 2
1 3
3 4
2 5
4 6
2 6
1 4
5 3
5 4
3 2

输出

6

样例解释

一种方案是选择 $3,6,5,1$参观，经过 $2+2+2=6$ 条道路。

数据范围

对于所有数据 $n\le 4000,m\le 5000,1\le x_i,y_i\le n$ ，保证无重边，自环。