Trang Trí Đồng Cỏ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 50 000$
$1 \leq M \leq 100 000$
$A_{i} \neq B_{i}$
Có thể có nhiều đường nối cùng một cặp đồng cỏ.

Ví dụ

Input	Output	Giải thích
4 4 1 2 2 3 3 4 4 1	2	Đồ thị là hình vuông (chu trình chẵn). Đặt J ở đỉnh 1, 3 và F ở đỉnh 2, 4 (hoặc ngược lại). Tối đa 2 biển J.

Bình luận

Không có bình luận tại thời điểm này.