Migrated from Lutece 2388 马队

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Macaron_lin 是一位驯马师，他一共有 $n$ 匹马，有些马之间存在矛盾。他想把所有马分成若干队伍进行比赛，每个队伍至少有 $1$ 匹马。为了避免内讧，他希望一个队伍内的马之间不能有矛盾。同时，为了让比赛进行得更激烈，他希望对于任意的两个队伍，从这两个队伍中各自任选出一匹马，这两匹马之间一定会有矛盾。请问他需要把这些马分成几个队伍？

Input

第一行输入两个整数 $n$ 和 $m$ ($2 \le n \le 1000, 1 \le m \le \frac{n(n-1)}{2}$)，表示有 $n$ 匹马和 $m$ 对矛盾关系。
接下来 $m$ 行，每行输入两个整数 $a$ 和 $b$ ($1 \le a,b \le n$ 且 $a \ne b$)，表示 $a$ 号马与 $b$ 号马之间存在矛盾。

Output

输出一个整数，表示需要把这些马分成几个队伍。如果无解输出 $-1$。

Samples

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

4

4 2
1 2
3 4

-1

Resources

cjj