Elearning CodePath – CTP Online Judge

Giao Hàng Trong Thành Phố (Mail Delivery)

DELIVERY

🟢 Hard #Graph

📌 Thông tin chung
Tên File Input	DELIVERY.INP
Tên File Output	DELIVERY.OUT
📝 Đề bài
Plaintext
Nhiệm vụ của bạn là đưa thư đến cư dân của một thành phố. Vì lý do này, bạn muốn tìm một lộ trình có điểm bắt đầu và điểm kết thúc đều là bưu điện, đồng thời lộ trình đó phải đi qua mọi con đường trong thành phố đúng một lần duy nhất.

Định dạng Đầu vào:
- Dòng đầu tiên chứa hai số nguyên n và m: số lượng điểm giao cắt và số lượng con đường. Các điểm giao cắt được đánh số 1, 2, ..., n và bưu điện nằm ở điểm giao cắt số 1.
- m dòng tiếp theo mô tả các con đường. Mỗi dòng chứa hai số nguyên a và b đại diện cho một con đường hai chiều nối giữa điểm giao cắt a và b.
- Mỗi con đường luôn nối giữa hai điểm giao cắt khác nhau và có tối đa một con đường giữa hai điểm bất kỳ.

Định dạng Đầu ra:
- In ra tất cả các điểm giao cắt trên lộ trình theo thứ tự bạn sẽ ghé thăm chúng. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
- Nếu không có giải pháp nào, in ra "IMPOSSIBLE".

Giới hạn:
- 2 <= n <= 10^5
- 1 <= m <= 2.10^5
- 1 <= a, b <= n

Ví dụ:
Input:
6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5

Output:
1 2 6 3 2 4 5 3 1

Subtask:
- Subtask 1 (40% số điểm): n <= 1000, m <= 2000.
- Subtask 2 (60% số điểm): n <= 10^5, m <= 2.10^5.

✅ Đã AC: 0 / 11 submissions