Migrated from Lutece 2958 你干嘛哎呦

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

世界上有五种好：早上好、中午好、下午好、晚上好、还有全民制作人们大家好。

Kun 是一位备受瞩目的音乐艺人，他有一个庞大的粉丝群体，自称 ikun。ikun 这个称号，不仅代表着对 Kun 的支持，更是团结的象征：每一位 ikun 都与其他所有的 ikun 有直接的联系。然而，总有一些人嫉妒哥哥的才华，他们被称为小黑子。为了与 ikun 们势均力敌，每一个小黑子同样都与其他所有的小黑子有直接的联系。作为 ikun 的你，你知道所有人的联系关系，但不知道谁是 ikun，谁是小黑子。 为了更好地支持哥哥，你迫切想知道两方人数之差的绝对值的最大值。 要注意一点， 在这个世界上，一个人如果不是 ikun，那么就是小黑子。可能所有人都是小黑子，也可能所有人都是ikun。

给定一张 $n$ 个点 $m$ 条边的无向图，你需要将所有点划分成两个部分，满足任意两个不同编号但同一部分的点之间有一条边直接相连。对于可能的两部分点数差的绝对值，输出其最大值。 若无解则输出 $-1$。

保证无自环和重边。

Input

第一行两个整数 $n,m$，表示图的点数和边数； 接下来 $m$ 行，每行两个整数 $x,y$，表示 $x$ 和 $y$ 有一条边相连。

Output

若有解输出一个整数表示可能的最大值；否则输出 $-1$。

Samples

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

0

3 3
1 2
2 3
1 3

3

3 0

-1

Constraints

$1 \leq n \leq 1000$, $0 \leq m \leq \frac{n(n-1)}{2}$ $1 \leq x, y \leq n$

Note

第一组数据可能是以下情况：1，2，3 为黑子，4，5，6 为 ikun， 只因子图 $\{1,2,3\}$，$\{4,5,6\}$ 及其相连的边均为完全图。 第二组数据可能是以下情况：1，2 , 3为黑子，无人为 ikun， 只因子图 $\{1,2,3\}$及其相连的边为完全图。 第三组数据如果有解，显然至少有两人是同一阵营，但他们之间无直接联系，不符合要求。 注意：黑子和 ikun 之间可以有直接联系。

Resources

2023 UESTC ICPC Training for Graph