Dịch vụ giao hàng
Đề bài
Mô tả
Công ty Bưu kiện Liên thành phố Caspian (ICPC) đang mở một dịch vụ giao hàng giữa các thành phố quanh biển Caspian. Công ty dự định thuê các người đưa hàng để mang bưu kiện giữa các thành phố này.
Mỗi người đưa hàng có một thành phố nhà và một thành phố đích, và mọi người đưa hàng có cùng một lịch trình di chuyển: rời thành phố nhà lúc 9:00, đến thành phố đích lúc 12:00, rời thành phố đích lúc 14:00 và trở về thành phố nhà lúc 17:00. Trong khi đang ở thành phố nhà hoặc thành phố đích, họ có thể nhận bưu kiện từ khách hàng và/hoặc giao bưu kiện cho khách hàng. Họ cũng có thể trao bưu kiện cho, hoặc nhận bưu kiện từ, những người đưa hàng khác đang có mặt ở cùng thành phố vào cùng thời điểm. Vì ICPC là dịch vụ tận tay, bưu kiện không bao giờ được để lại ở kho hay nơi nào khác để lấy sau: trừ khi bưu kiện đã tới đích, người đưa hàng phải hoặc tự giữ bưu kiện (trong ngày hoặc qua đêm), hoặc trao nó cho một người đưa hàng khác.
Công ty sẽ chỉ đạo các người đưa hàng trao tay bưu kiện sao cho mọi bưu kiện luôn có thể được giao tới đích. Ít nhất là họ hy vọng như vậy!
Ta nói hai thành phố và được kết nối nếu có thể giao một bưu kiện từ thành phố tới thành phố và cũng có thể giao từ tới . Để đánh giá hiệu quả của quá trình tuyển dụng, sau mỗi lần thuê thêm một người đưa hàng, công ty muốn biết số cặp thành phố được kết nối ().
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó () là số thành phố và () là số người đưa hàng sẽ được thuê. Các người đưa hàng được đánh số từ đến theo thứ tự được thuê.
Tiếp theo là dòng, dòng thứ chứa hai số nguyên phân biệt và (), lần lượt là thành phố nhà và thành phố đích của người đưa hàng thứ .
Dữ liệu ra
In ra số nguyên, mỗi số trên một dòng: số cặp thành phố được kết nối sau khi đã thuê người đưa hàng đầu tiên.
Ràng buộc
- , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 1 2 2 3 4 3 4 2 |
1 2 4 6 |
Sau người thứ nhất, thành phố và được kết nối. Sau người thứ hai, và được kết nối, nhưng và thì chưa: hai người đưa hàng (đi giữa và giữa ) không bao giờ gặp nhau. Sau người thứ ba, thêm các cặp và ; chẳng hạn từ tới : lúc 19:00 trao bưu kiện cho người thứ hai ở thành phố ; trưa hôm sau người này tới thành phố và trao cho người thứ ba cũng đang ở đó; lúc 18:00 người thứ ba mang bưu kiện về thành phố . Sau người thứ tư, cả cặp đều được kết nối. |
| 3 3 1 2 2 1 3 1 |
1 1 3 |
Người thứ hai (nhà ở , đích ở ) không gặp người thứ nhất (người thứ nhất ở khi người thứ hai ở và ngược lại), nên vẫn chỉ có cặp . Người thứ ba ở thành phố vào buổi trưa, gặp người thứ hai, nên cả ba cặp đều được kết nối. |
Bình luận