← 返回题目列表

Codeforces · 574/B

B. 熊和三个火枪手

中文机器翻译题面 查看原题

你知道三个火枪手的故事吗?无论如何,您现在将了解它的起源。

Richelimakieu 是贝尔里斯市的一位红衣主教。他厌倦了独自处理犯罪问题。他需要三个勇敢的战士来帮助他对抗坏人。

有n个战士。 Richelimakieu想选择其中三个人成为火枪手,但这并不容易。最重要的条件是火枪手必须相互了解才能高效合作。而且他们不应该太出名,因为他们可能会被老朋友背叛。对于每个火枪手来说,他的认可是他认识的战士数量,不包括其他两名火枪手。

帮助Richelimakieu!求是否可以选择三个互相认识的火枪手,以及他们的认识的最小可能总和是多少。

输入

第一行包含两个空格分隔的整数 n 和 m (3 ≤ n ≤ 4000, 0 ≤ m ≤ 4000) — 分别是战士的数量和彼此认识的战士对的数量。

以下 m 行中的第 i 行包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。武士ai和bi互相认识。每对战士最多被列出一次。

输出

如果 Richelimakieu 可以选择三个火枪手,请打印他们的认可的最小可能总和。否则,打印“-1”(不带引号)。

示例

输入 #1

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

输出 #1

2

输入 #2

7 4
2 1
3 6
5 1
1 7

输出 #2

-1

注意

在第一个样本中,Richelimakieu 应该选择三重 1, 2, 3。第一个火枪手除了其他两个火枪手之外不认识任何人,因此他的识别度为 0。第二个火枪手有识别度 1,因为他知道战士编号 4。第三个火枪手也有识别度 1,因为他认识战士 4。识别度之和为 0 + 1 + 1 = 2。

另一个可能的三元组是 2, 3, 4,但它的识别总和更大,等于 1 + 1 + 1 = 3。

在第二个样本中,没有三个互相认识的战士。