#3618. 黑马篮球队

黑马篮球队

题目描述

三人篮球起源于美国街头黑人孩子的三对三斗牛赛,是一项孩子们创造的竞技活动。目前有n n 个球员,其中有 mm 对相互认识的关系。一个球员的知名度定义为有多少人和他相互认识。

现在教练需要从这 nn 个球员中选出三个人成为一支黑马球队参加比赛,需要球队三人相互认识,但是教练又希望他们三个人的知名度总和加起来最低,到时给大家来一个“一鸣惊人”。

输入

第一行为两个整数 n,mn,m,都不大于 4000。

往后 mm 行每一行输入两个不超过n n 的整数 x,y(x<y)x,y(x < y),表示第 x,yx,y两人互相认识(数据中有可能会有重复的认识关系)。

输出

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

第二行包括一个数据:图中边的总数。

样例

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

数据范围

  • 对于 50% 的数据,满足n,m200n,m≤200
  • 对于 100% 的数据,满足n,m40000n,m≤40000

来源

  • 一本通编程启蒙在线评测