Vừa đủ cầu
Đề bài
Mô tả
Kiến Chimera là một loài thông minh và chăm chỉ.
Có một đàn gồm con Kiến Chimera sống gần sông Hàn ở Đà Nẵng, Việt Nam. Chúng đã xây ngôi nhà (mỗi con kiến một nhà) ở một bên bờ sông Hàn, và bãi kiếm ăn ở bờ bên kia. Các ngôi nhà được đánh số từ đến , các bãi kiếm ăn cũng được đánh số từ đến .
Đàn kiến cũng đã xây cây cầu bắc qua sông Hàn (), mỗi cây cầu nối một ngôi nhà với một bãi kiếm ăn. Có thể có nhiều hơn một cây cầu nối cùng một ngôi nhà với cùng một bãi kiếm ăn.
Mỗi sáng, con kiến chọn cây cầu để đi từ nhà của mình tới các bãi kiếm ăn.
Các cây cầu được xây sao cho đàn kiến có thể đi thẳng tới cả bãi kiếm ăn. Nói cách khác, tồn tại một hoán vị của các số nguyên từ đến sao cho với mọi , có một cây cầu nối ngôi nhà thứ với bãi kiếm ăn thứ .
Đàn kiến cảm thấy chúng đã xây quá nhiều cầu. Vì vậy chúng muốn dỡ bỏ đúng một cây cầu sao cho điều kiện trên vẫn được thỏa mãn.
Dù rất thông minh, Kiến Chimera lại không giỏi tính toán. Hãy giúp đàn kiến đếm xem có bao nhiêu cây cầu khác nhau có thể dỡ bỏ.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và ().
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (): có một cây cầu nối ngôi nhà thứ với bãi kiếm ăn thứ .
Dữ liệu đảm bảo tồn tại hoán vị như mô tả ở trên.
Dữ liệu ra
In ra số cây cầu thỏa mãn điều kiện.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 1 1 2 2 2 |
1 | Hoán vị duy nhất là , dùng các cầu và . Chỉ có thể dỡ cầu . |
| 3 6 1 1 2 2 3 3 1 2 2 3 1 3 |
3 | Ví dụ bổ sung (không có trong đề gốc). Hoán vị duy nhất là , nên có thể dỡ một trong ba cầu , , . |
Bình luận