Đường ống thoát nước
Đề bài
Mô tả
Trong một tòa nhà chung cư, người ta thiết kế một hệ thống thoát nước bao gồm chốt được đánh số cùng với đường ống hai chiều nối giữa cặp chốt có dạng với và . Hệ thống là "đạt yêu cầu" nếu như từ mỗi chốt, nước đều có thể chảy đến tất cả các chốt khác thông qua các đường ống. Nguyên tắc hoạt động của hệ thống là: ban đầu hệ thống sẽ không có nước, mỗi khi có nước chảy vào từ một chốt nào đó, nước sẽ thoát ra qua các chốt được nối trực tiếp với chốt thông qua các đường ống. Cứ tiếp tục như thế, nước sẽ chảy lan ra toàn hệ thống và có xu hướng chảy càng lúc càng xa chốt chứ không chảy ngược lại. Nếu nước chảy đến một chốt nào đó mà không chảy đi được nữa thì dừng lại tại đó.
Ban quản lý muốn bỏ bớt đúng một đường ống để hệ thống vẫn đạt yêu cầu và ứng với cách bỏ đó, tồn tại cách chọn chốt thích hợp để mỗi khi có nước chảy vào thì ở mọi chốt trong hệ thống, nước sẽ đều chảy đến được và sẽ thoát ra từ chốt đó bằng không quá chốt khác.
Như vậy, tại chốt nước thoát ra qua mọi chốt nối trực tiếp với ; tại mỗi chốt khác, nước không chảy ngược về chốt mà nó vừa chảy đến từ đó, nên chốt này không được tính vào chốt nói trên.
Yêu cầu: Hãy viết chương trình xác định số cách chọn bỏ đi một đường ống nào đó để hệ thống còn lại vẫn đảm bảo các yêu cầu trên.
Dữ liệu vào
- Dòng thứ nhất chứa hai số nguyên ().
- Trên dòng tiếp theo, mỗi dòng chứa một cặp số cho biết có đường ống nước nối giữa chốt và chốt . Hệ thống ban đầu đảm bảo đạt yêu cầu và các cặp phân biệt nhau giữa các dòng (không có hai đường ống nào nối cùng một cặp chốt).
Dữ liệu ra
In ra một số nguyên là số cách bỏ đường ống.
Ràng buộc
- .
- , .
- Hệ thống ban đầu đạt yêu cầu, không có hai đường ống nào nối cùng một cặp chốt.
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): và .
- Subtask 4 ( số điểm): .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 2 1 2 2 3 3 4 4 5 3 1 3 6 2 7 2 8 |
1 | Ta có cách bỏ đường ống như sau: bỏ đường ống nối và chọn chốt là . Khi đó, nước sẽ chảy từ chốt đến , từ đây thoát ra chốt và ; tiếp theo, từ chốt chảy đến ; từ chốt chảy đến chốt và ; cuối cùng là từ chốt đến . Nếu bỏ đường ống nối chốt thì cho dù chọn chốt là chốt nào thì khi đến chốt , nước sẽ thoát ra theo ít nhất chốt khác (tức là lớn hơn ). Tương tự nếu bỏ đường ống thì cho dù chọn chốt là chốt nào thì khi đến , nước sẽ thoát ra theo ít nhất chốt khác. Ngoài ra, nếu bỏ bất kỳ đường ống nào khác thì hệ thống sẽ không còn đạt yêu cầu nữa. |
| 3 1 1 2 2 3 3 1 |
3 | Bỏ đường ống nào cũng được, ví dụ bỏ và chọn : nước chảy từ đến rồi từ đến , mỗi chốt thoát ra qua không quá chốt khác. |
| 5 1 1 2 2 3 3 4 4 1 1 5 |
2 | Bỏ và chọn : nước chảy . Tương tự với cách bỏ . Bỏ hoặc thì chốt nối với chốt, nước luôn thoát ra từ qua ít nhất chốt. Bỏ thì chốt không nhận được nước. |
Bình luận