Alexander 准备在他的计算机上安装一个名为 Burnished Security Updates (BSU) 的重要更新包。他拥有的网络由 $n$ 台计算机和 $m$ 条双向电缆连接而成。

最终，BSU 将被安装在网络中的每一台计算机上。但 Alexander 不知道更新后系统会如何表现，因此他将首先在一个满足以下条件的非空计算机集合上安装更新：

• 任意两台已更新的计算机之间都没有电缆直接相连；
• 每条电缆至少有一个端点是已更新的计算机；
• 已更新计算机的集合大小必须尽可能小。

形式化地说，如果我们用图来表示计算机网络，Alexander 想要找到该图的一个独立集，使得它同时也是该图的一个点覆盖。在所有可能的集合中，他希望选择一个大小最小的集合。

现在，你需要帮助 Alexander 找出安装 BSU 的计算机数量。注意，有时可能根本无法找到满足上述条件的集合。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示计算机的数量和电缆的数量 ($2 \le n \le 3 \cdot 10^5$, $1 \le m \le 3 \cdot 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 条电缆的两个端点 ($1 \le x_i, y_i \le n$, $x_i \neq y_i$)。

保证每对计算机之间最多只有一条电缆相连。

输出格式

如果不存在这样的集合，输出一个整数 $-1$。

否则，输出所需计算机集合的大小。

样例

样例输入 1

4 2
1 2
3 4

样例输出 1

2

样例输入 2

4 4
1 2
2 3
3 4
1 4

样例输出 2

2

样例输入 3

4 3
1 2
2 3
1 3

样例输出 3

-1