Farmer John có $N$ đồng cỏ ($1 \leq N \leq 50,000$), đánh số $1...N$, nối bằng $M$ đường hai chiều ($1 \leq M \leq 100,000$). Đường $i$ nối $A_i$ ($1 \leq A_i \leq N$) với $B_i$ ($1 \leq B_i \leq N$), với $A_i != B_i$. Hai đường có thể nối cùng một cặp.

Bessie trang trí cho sinh nhật FJ. Muốn mỗi đồng có bảng lớn '$F$' hoặc '$J$', nhưng để không làm ông nhầm, hai đồng nối bằng đường phải dùng chữ khác nhau.

Công ty tính '$F$' đắt hơn '$J$', nên cô muốn tối đa số '$J$'. Tìm số đó hoặc in -1 nếu không có cách xếp hợp lệ.

Dữ liệu vào

• Dòng 1: số nguyên $N$, $M$.
• Dòng $2..M+1$: số nguyên $A_i$, $B_i$, chỉ đường hai chiều giữa $A_i$ và $B_i$.

Dữ liệu ra

• Dòng 1: số nguyên là số bảng '$J$' lớn nhất. Nếu không có lời giải hợp lệ, in -1.

Ví dụ

Dữ liệu vào 1

4 4
1 2
2 3
3 4
4 1

Dữ liệu ra 1

2

Ghi chú

Đồng và đường tạo thành đỉnh và cạnh một hình vuông.

Bessie có thể chọn đồng 1 và 3 mang '$J$', hoặc thay bằng 2 và 4.

Tác giả bài toán: Kalki Seksaria, 2014