CF574B Bear and Three Musketeers

你知道“三剑客”的故事吗？无论如何，你现在将了解它的起源。 Richelimakieu 是 Bearis 城市的一位红衣主教。他已经厌倦了独自一人对抗犯罪。他需要三位勇敢的战士来协助他与坏人作战。 有 $n$ 个战士。Richelimakieu 想从中选出三人担任“三剑客”，但这并不容易。最重要的条件是，这三位剑客必须互相认识，才能高效合作。同时，他们又不能太过有名，否则可能被老朋友背叛。对于每一位剑客来说，ta 的“知名度”是指除去另外两位剑客后，他认识的战士数量。 请你帮 Richelimakieu！判断是否有可能选出三位彼此相识的剑客，并求出他们的“知名度”之和的最小值。

第一行包含两个空格分隔的整数 $n$ 和 $m$（$3 \leq n \leq 4000$，$0 \leq m \leq 4000$），分别表示战士人数和相识的战士对数。 接下来的 $m$ 行中，第 $i$ 行包含两个空格分隔的整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示战士 $a_i$ 与 $b_i$ 互相认识。每对战士至多出现一次。

如果 Richelimakieu 可以选出三位彼此相识的剑客，输出他们的“知名度”之和的最小值。否则，输出 $-1$。

在第一个样例中，Richelimakieu 应当选择 $1, 2, 3$ 这组三剑客。第一个剑客除了其余两剑客外不认识其他人，因此他的知名度为 $0$。第二个剑客认识 $4$ 号战士，所以他的知名度为 $1$。第三个剑客也认识 $4$ 号战士，所以知名度为 $1$。知名度之和为 $0+1+1=2$。 另一组三剑客为 $2, 3, 4$，但其知名度之和为 $1+1+1=3$，更大。 第二个样例中，没有三位彼此相识的战士。 由 ChatGPT 5 翻译