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