Farmer John 有 $N$ 个牧场（$1 \leq N \leq 50,000$），编号 $1...N$，由 $M$ 条双向路径连接（$1 \leq M \leq 100,000$）。路径 $i$ 连接 $A_i$（$1 \leq A_i \leq N$）和 $B_i$（$1 \leq B_i \leq N$），且 $A_i != B_i$。同一对牧场可以有两条路径连接。

Bessie 决定为 FJ 生日装饰牧场。她想在每个牧场放一个写着字母 '$F$' 或 '$J$' 的大牌子，但为免 FJ 混淆，路径相连的两个牧场必须用不同字母。

牌子公司对 '$F$' 收费高于 '$J$'，因此她想使用尽可能多的 '$J$'。求其最大数量；若无法合法布置，输出 -1。

输入格式

• 第 1 行：两个整数 $N$ 和 $M$。
• 第 $2..M+1$ 行：两个整数 $A_i$ 和 $B_i$，表示 $A_i$ 与 $B_i$ 间有双向路径。

输出格式

• 第 1 行：一个整数，表示可用 '$J$' 牌子的最大数量。若无合法方案，输出 -1。

样例

输入格式 1

4 4
1 2
2 3
3 4
4 1

输出格式 1

2

说明

牧场和路径形成一个正方形的顶点和边。

Bessie 可以将牧场 1 和 3 标为 '$J$'，或改选牧场 2 和 4。

题目作者：Kalki Seksaria，2014