题目描述

农民约翰有${N（}$${1<=N<=50000）}$个牧场，编号为${1...}$${N}$、 由${M（}$${1<=M<=100000）}$条双向路径连接。路径${i}$将牧场${A_i（}$${1<=A_i<=N）}$连接到牧场${B_i（}$${1<=B_i<=N）}$和${A_i！}$${=B_i.}$同一对牧场之间可能有两条路径连接。贝西决定为${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}$。

样例

输入样例

4 4
1 2
2 3
3 4
4 1

输出样例

2