Những tour riêng biệt
Đề bài
Mô tả
Thành phố Hà Nội có điểm tham quan, được đánh số từ đến . Có con đường hai chiều nối các điểm tham quan. Các con đường này tạo thành một đơn đồ thị: không có hai con đường nào nối cùng một cặp điểm, và không có con đường nào nối một điểm với chính nó.
Mỗi con đường được trang trí bằng một loại cây khác nhau. Hạnh là người yêu cây và muốn tạo ra một tập gồm tour thỏa mãn:
- Mỗi tour là một chu trình độ dài () đi qua điểm tham quan . Cụ thể hơn:
- với mọi mà , và phải được nối trực tiếp bởi một con đường;
- và cũng phải được nối trực tiếp bởi một con đường;
- các đôi một phân biệt.
- Mỗi tour phải có ít nhất một con đường không thuộc bất kỳ tour nào trong tour còn lại.
Hạnh nhận ra rằng có thể không tạo được tập tour như vậy với mạng lưới đường hiện tại. Vì vậy, Hạnh muốn xây thêm một số con đường hai chiều sao cho:
- Tập đường mới (gồm cả đường xây thêm và đường ban đầu) vẫn tạo thành một đơn đồ thị: không có hai con đường nào nối cùng một cặp điểm, và không có con đường nào nối một điểm với chính nó.
- Số con đường xây thêm là ít nhất.
Hãy giúp Hạnh xây thêm đường và tạo một tập tour.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (), cho biết ban đầu có một con đường nối hai điểm và . Dữ liệu đảm bảo con đường này tạo thành một đơn đồ thị.
Dữ liệu ra
Nếu không thể tạo một tập tour dù Hạnh xây thêm đường như thế nào, in ra một dòng duy nhất chứa từ NO. Ngược lại:
- Dòng đầu tiên chứa từ YES.
- Dòng thứ hai chứa một số nguyên , số con đường xây thêm ít nhất.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (), cho biết xây thêm một con đường nối hai điểm và .
- dòng cuối cùng, mỗi dòng mô tả một tour theo định dạng sau:
- Số nguyên đầu tiên là , số điểm tham quan của tour.
- số nguyên tiếp theo là , các điểm tham quan của tour.
Nếu có nhiều phương án tối ưu, bạn có thể in ra phương án bất kỳ.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 3 1 2 1 3 1 4 2 4 |
YES 2 2 3 3 4 3 2 1 3 3 2 1 4 3 3 1 4 |
Xây thêm hai đường và . Ba tour , , lần lượt có đường riêng , , không thuộc hai tour còn lại. |
| 3 3 3 1 2 1 3 2 3 |
NO | Các đường hiện tại tạo thành đồ thị đầy đủ nên không thể xây thêm đường nào. Chỉ có thể tạo tour dùng tất cả các đường hiện có. |
Bình luận