你知道三个火枪手的故事吗?无论如何,您现在将了解它的起源。
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。
在第二个样本中,没有三个互相认识的战士。