Trang Trí Đồng Cỏ

Có $N$ đồng cỏ được nối bởi $M$ con đường hai chiều. Cần đặt biển hiệu vào mỗi đồng cỏ, mỗi biển ghi chữ F hoặc J, sao cho hai đồng cỏ kề nhau (có đường nối trực tiếp) phải ghi chữ khác nhau.

Vì biển F đắt hơn biển J, hãy tìm cách đặt sao cho số biển J là lớn nhất có thể. Nếu không thể đặt hợp lệ, in $-1$.

Dữ liệu vào

• Dòng đầu tiên: hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $A_i$ và $B_i$, biểu thị một con đường nối đồng cỏ $A_i$ và $B_i$.

Dữ liệu ra

Một số nguyên duy nhất — số biển J tối đa, hoặc $-1$ nếu không tồn tại cách đặt hợp lệ.

Ràng buộc

• $1\le N\le 50000$
• $1\le M\le 100000$
• $A_i\ne B_i$
• Có thể có nhiều đường nối cùng một cặp đồng cỏ.

Ví dụ