给定一组相互交往的人，我们可以定义一个图，其顶点为这些人，当且仅当两人互为朋友时，它们之间存在一条边。这样的图被称为社交网络，在任何人群集合上都有明确的定义，例如大学里的学生或小镇的居民。近年来，一门分析社交网络的完整科学已经兴起，因为人们及其行为的许多有趣方面最好理解为这种友谊图的属性。

给定一个友谊图，其中顶点是“问题解决”课程的学生，你的任务是编写一个程序，将班级中的学生划分为两个组 $A$ 和 $B$，使得以下三个条件同时满足：

• 每个学生恰好属于一个组，$A$ 或 $B$。
• 每个组内的任意两人都互为朋友。
• 两个组的大小之差，记为 $||A| - |B||$，尽可能小。

例如，假设我们得到如下图所示的友谊图。将学生划分为 $A = \{u_1, u_2, u_3, u_6\}$ 和 $B = \{u_4, u_5, u_7\}$ 是不可能的，因为 $u_2$ 和 $u_6$ 不是朋友。另一方面，在划分为 $A = \{u_1, u_2\}$ 和 $B = \{u_3, u_4, u_5, u_6, u_7\}$ 时，每个组内的任意两人都互为朋友；然而，两个组之间的大小差 $(|2 - 5| = 3)$ 大于划分为 $A = \{u_1, u_2, u_3\}$ 和 $B = \{u_4, u_5, u_6, u_7\}$ 时的差 $(|3 - 4| = 1)$。后者是我们想要的最佳划分。

输入格式

程序应从标准输入读取数据。第一行包含两个整数 $n$ 和 $m$，分别表示友谊图的顶点数和边数，其中假设 $2 \le n \le 1,000$ 且 $0 \le m \le \binom{n}{2}$。顶点编号从 $1$ 到 $n$。接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$，表示图中的一条边 $(u, v)$。

输出格式

程序应向标准输出写入数据。打印一行，包含一个整数。如果学生可以被划分为满足上述三个条件的两个组，则该整数应为两个组大小之差的最小值；否则，该整数应为 $-1$。

样例

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

-1

样例输入 3

4 4
4 3
3 2
2 1
1 4

样例输出 3

0