为了提供更好的饮用水质量，政府计划在供水系统中部署一些“智能设备”，以便监测水质。供水系统由许多管道组成，两条管道通过一个接头连接。你可以假设该系统构成一个连通的简单图，其中管道为边，接头为顶点。下图展示了一个示例。

智能设备被设计部署在接头上。然而，两个相邻的设备可能会相互干扰，因此要求任意两个设备不能相邻。为了使系统能够被完全监测，必须部署足够数量的设备。形式上，如果满足以下条件，则称系统被完全监测：

• 部署的设备数量至少为 $n - 28$ 个，且
• 任意两个设备互不相邻。

请判断该系统是否可以被完全监测。如果不能，输出 $-1$；否则，输出可以部署的设备的最大数量。

输入格式

输入文件的第一行包含两个正整数 $n$ 和 $m$，其中 $n$ 是接头的数量（编号从 $0$ 到 $n - 1$），$m$ 是管道的数量。接下来的 $m$ 行，每行包含两个非负整数，表示管道两端的接头编号。

输出格式

输出一个整数：如果系统无法被完全监测，则输出“-1”；否则，输出可以部署的设备的最大数量。

数据范围

• $2 \le n \le 3 \times 10^4$
• $1 \le m \le 5 \times 10^5$

样例

输入 1

5 7
1 0
2 3
1 4
1 2
3 1
3 4
0 4

输出 1

2