Farmer John có \(N\) đồng cỏ (\(1 \le N \le 50\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\), nối với nhau bằng \(M\) lối đi hai chiều (\(1 \le M \le 100\,000\)). Lối đi thứ \(i\) nối đồng cỏ \(A_i\) (\(1 \le A_i \le N\)) với đồng cỏ \(B_i\) (\(1 \le B_i \le N\)), trong đó \(A_i \ne B_i\). Có thể có hai lối đi nối cùng một cặp đồng cỏ.

Bessie quyết định trang trí các đồng cỏ nhân dịp sinh nhật Farmer John. Cô muốn đặt tại mỗi đồng cỏ một tấm biển lớn mang chữ F hoặc chữ J. Tuy nhiên, để Farmer John không bị nhầm lẫn, cô muốn bảo đảm rằng hai đồng cỏ được trang trí bằng hai chữ khác nhau nếu chúng được nối trực tiếp bởi một lối đi.

Công ty làm biển đòi Bessie trả nhiều tiền hơn cho biển chữ F so với biển chữ J, vì vậy Bessie muốn dùng nhiều biển chữ J nhất có thể. Hãy xác định số lượng biển chữ J lớn nhất, hoặc in ra \(-1\) nếu không tồn tại cách bố trí biển hợp lệ.

Dữ liệu vào

• Dòng đầu tiên chứa 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\), cho biết có một lối đi hai chiều nối \(A_i\) với \(B_i\).

Ràng buộc

• \(1 \le N \le 50\,000\).
• \(1 \le M \le 100\,000\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\).
• Có thể có hai lối đi nối cùng một cặp đồng cỏ.

Dữ liệu ra

• In ra số lượng biển chữ J lớn nhất mà Bessie có thể dùng. Nếu không có cách bố trí biển hợp lệ, in ra \(-1\).

Ví dụ

4 4
1 2
2 3
3 4
4 1

2

Nguồn

USACO 2014 US Open, Bronze — Problem 3: Decorating the Pastures

Tác giả đề: Kalki Seksaria, 2014.