配点 : $700$ 点

問題文

AtCoder 連邦の高橋州には，$N$ 個の都市があります．都市は $1, 2, ..., N$ と番号付けされています． これらの都市の間は，$M$ 本の両方向に行き来可能な道で結ばれています． $i$ 番目の道は都市 $A_i$ と都市 $B_i$ の間を結んでいます． どの道も，異なる都市間を結んでいます． また，どの都市間にも，それらを直接結ぶ道は高々 $1$ 本しか存在しません．

ある時，高橋州は高州と橋州の $2$ つの州に分かれることになりました． 高橋州の各都市は，分離後は高州もしくは橋州のいずれか片方に属することになります． ここで，すべての都市が高州，または橋州の一方のみに属してしまっても構わないことにします． このとき，次の条件を満たすようにしたいです：

• 高州，橋州のいずれにおいても，同じ州内では，どの $2$ つの都市も 直接 道で結ばれている．

両端の都市が同じ州内に属しているような道の本数として考えられるもののうち，最小のものを求めてください． ただし，条件を満たすように都市を高州，橋州に分けることが不可能なら，-1 を出力してください．

制約

• $2 \leq N \leq 700$
• $0 \leq M \leq N(N-1)/2$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq N$
• $A_i \neq B_i$
• $i \neq j$ のとき，$A_i \neq A_j$ または $B_i \neq B_j$ の少なくとも片方が成立
• $i \neq j$ のとき，$A_i \neq B_j$ または $B_i \neq A_j$ の少なくとも片方が成立

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_M$ $B_M$

出力

答えを出力せよ．

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

4

例えば，高州に都市 $1, 2$ を，橋州に都市 $3, 4, 5$ を割り当てると，条件を満たします． このとき，両端の都市が同じ州内に属しているような道の本数は $4$ になります．

5 1
1 2

-1

この例では，どのように都市を割り当てても，条件を満たすことができません．

4 3
1 2
1 3
2 3

3

10 39
7 2
7 1
5 6
5 8
9 10
2 8
8 7
3 10
10 1
8 10
2 3
7 4
3 9
4 10
3 4
6 1
6 7
9 5
9 7
6 9
9 4
4 6
7 5
8 3
2 5
9 2
10 7
8 6
8 9
7 3
5 3
4 5
6 3
2 10
5 10
4 2
6 2
8 4
10 6

21