Quảng cáo

Points: 0.14 (partial)

Time limit: 0.38s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

Hứa Lê Thanh Vy

Problem type

Allowed languages

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

Nhân dịp Tết sắp đến công ty Jelly-for-Kids quyết định tăng cường việc quảng bá sản phẩm đến người tiêu dùng. Vì thế giám đốc marketing, ông Fruit-Jelly muốn gửi đi số lượng nhân viên tối đa có thể, làm nhiệm vụ tiếp thị tại đại lý trong thành phố

Trong thành phố có ~m~ con đường, ~n~ đại lý bán kẹo (đánh số từ ~1~ đến ~n)~. Mỗi con đường chỉ nối trực tiếp giữa ~2~ đại lý, và được ký hiệu bằng chỉ số của ~2~ đại lý mà nó nối. Đồng thời, giữa ~2~ đại lý bất kỳ có không quá ~1~ con đường nối chúng

Ông Fruit-Jelly nghĩ rằng, ông ta sẽ quản lý nhân viên dễ hơn nếu xếp mỗi người tiếp thị trên những hành trình có tính chất thứ tự. Tức là những đại lý bán kẹo trên hành trình đó thỏa các điều kiện sau:

Có đường nối trực tiếp giữa ~2~ đại lý liên tiếp nhau trên hành trình
Từ một đại lý bất kỳ trong hành trình có thể đi qua tất cả các đoạn đường trong hành trình đó rồi trở về nơi xuất phát mà không đi qua đoạn đường nào quá một lần
Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.

Mỗi nhân viên chỉ di chuyển trên hành trình mà anh ta được phân công. Hãy tính số lượng nhân viên tối đa mà ông Fruit-Jelly có thể xếp việc, và hành trình cụ thể mà mỗi người được xếp.

Input

Dòng đầu là ~2~ số tự nhiên ~N~ và ~M~ ~(N \le 2000)~ ~(M \le 5000)~

Trong ~M~ dòng tiếp theo, mỗi dòng ghi ~2~ số nguyên mô tả một đoạn đường, mỗi đoạn đường được mô tả bởi chỉ số của ~2~ đại lý mà nó nối.

Output

Dòng đầu tiên ghi ~Q~ là số lượng nhân viên tối đa tìm được

Sample Input

Sample Output

Comments

Please read the guidelines before commenting.

-3

vendettas commented on Nov. 2, 2024, 5:01 a.m.

skibidi dom dom yes yes

-2

quan08 commented on Sept. 1, 2024, 9:21 a.m.

cũng khó mà không quá dễ

-23

Khoipu commented on June 1, 2023, 8:07 a.m.

Cho mình hỏi là tại sao kq bài toán lại là m-n+k với k là số thành phần liên hông vậy ạ, mình vẫn chưa hiểu lắm

This comment is hidden due to too much negative feedback. Show it anyway.

-35

AMS21_22 commented on Aug. 19, 2022, 2:48 p.m.

bruh

This comment is hidden due to too much negative feedback. Show it anyway.

-33

Helu commented on Jan. 19, 2022, 7:17 a.m.

;-;

This comment is hidden due to too much negative feedback. Show it anyway.

-15

nguyenphong233 commented on Nov. 19, 2021, 2:00 p.m.

~~ bài hay quá ~~

This comment is hidden due to too much negative feedback. Show it anyway.

-44

phong23306mm commented on Oct. 23, 2021, 11:43 a.m.

:))

This comment is hidden due to too much negative feedback. Show it anyway.

-17

nguyenhainam1012cg commented on Jan. 19, 2023, 4:56 p.m.

=)))

This comment is hidden due to too much negative feedback. Show it anyway.

-134

namle commented on April 22, 2021, 3:10 a.m. ← edited →

NO

This comment is hidden due to too much negative feedback. Show it anyway.

-38

kennikai commented on March 4, 2022, 10:29 p.m.

YES

This comment is hidden due to too much negative feedback. Show it anyway.