Problem5394--三个火枪手

5394: 三个火枪手

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

nnn 个人,其中有 mmm 对相互认识的关系。
一个人的知名度定义为 有多少人 和他相互认识。
现在老师需要从这 nnn 个人中选出三个人成为火枪手,需要相互认识,但是在这个基础上又希望他们三个人的知名度总和加起来最低。

Input

第一行为两个整数 n,mn,mn,m,都不大于 400040004000
往后 mmm 行每一行输入两个不超过 nnn 的整数 x,y(x<y)x,y(x<y)x,y(x<y),表示第 x,yx,yx,y 两人互相认识(数据中有可能会有重复的认识关系)。
对于 50%50\%50% 的数据,满足 n,m≤200n,m\le 200n,m200
对于 100%100\%100% 的数据,满足 n,m≤4000n,m\le 4000n,m4000

Output

如果能找到三个相互认识的人,你需要输出所有选择中 知名度总和的最低值,否则输出 −1-11

Sample 1 Input

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

Sample 1 Output

8

Source/Category