[DMH_HSG_VP_24] Quần đảo
Xem dạng PDFQuốc gia X gồm ~N~ hòn đảo (đánh số từ ~1~ đến ~N~) xếp thành một hàng dài từ trái sang phải. Những hòn đảo này được nối với nhau bởi các cây cầu. Cây cầu thứ ~i~ nối hòn đảo thứ ~i~ với hòn đảo thứ ~i + 1~.
Một ngày nọ, giữa một số cặp hòn đảo đã xảy ra tranh chấp, nhà vua quyết định dỡ bỏ một số cây cầu để không có cách nào di chuyển giữa các hòn đảo xung đột nữa. Có nhiều cách để dỡ cầu thoả mãn điều kiện trên, nhưng nhà vua cần bạn giúp ông ấy tìm ra cách dỡ bỏ ít cây cầu nhất nhằm mục đích tiết kiệm chi phí.
Yêu cầu
Viết chương trình tìm số cây cầu ít nhất cần dỡ bỏ theo yêu cầu của nhà vua.
Dữ liệu đầu vào
Gồm ~M + 1~ dòng:
- Dòng 1: gồm hai số nguyên ~N,\ M~ ~(2 \le N \le 10^5;\ 1 \le M \le 10^5)~ ứng với số hòn đảo của quốc gia X và số cặp hòn đảo xảy ra xung đột;
- Tiếp theo là ~M~ dòng, mỗi dòng gồm hai số nguyên ~a_i,\ b_i~ ~(1 \le a_i, b_i \le N;\ a_i \ne b_i)~ mô tả một cặp hòn đảo xảy ra xung đột. Tất cả các cặp ~(a_i, b_i)~ này đôi một phân biệt.
Dữ liệu đầu ra
Gồm một số nguyên duy nhất là số cây cầu ít nhất cần dỡ bỏ theo yêu cầu của nhà vua.
Ví dụ
Ví dụ 1
INPUT
5 2
1 4
2 5
OUTPUT
1
Giải thích: Chỉ cần loại bỏ cây cầu nối giữa cặp hòn đảo ~(2, 3)~.
Bình luận
.
=>
hi ae