Elearning CodePath – CTP Online Judge

Hành trình qua những con đường đồi

WALKING

🟢 Easy #Graph

### Bài toán
Kamal vừa chuyển đến làm việc tại thành phố Chittagong. Để rèn luyện sức khỏe, mỗi buổi sáng anh ấy đều đi bộ qua các con đường đồi dốc tuyệt đẹp của thành phố. Chittagong có rất nhiều con đường và Kamal muốn mỗi sáng sẽ chọn những lộ trình khác nhau.

Tuy nhiên, khi chọn lộ trình, anh ấy luôn tuân thủ quy tắc: không đi qua bất kỳ con đường nào quá một lần (kể cả lượt về). Một điểm giao cắt giữa các con đường không được coi là một phần của con đường đó.

Vào một buổi sáng nọ, Kamal nảy ra ý tưởng: liệu anh ấy có thể đi tham quan tất cả các con đường của thành phố chỉ trong một lần đi bộ duy nhất hay không? Hành trình phải bắt đầu và kết thúc tại cùng một địa điểm (nhà của anh ấy).

Yêu cầu: Hãy giúp Kamal xác định xem có thể thực hiện được hành trình đi qua mọi con đường, mỗi đường đúng một lần và quay trở về điểm xuất phát hay không.

### Định dạng Đầu vào
Dữ liệu vào từ file WALKING.INP gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng hai số nguyên:
* Số nguyên N: số lượng điểm giao cắt (2 <= N <= 200). Các điểm giao cắt được đánh số từ 0 đến N-1.
* Số nguyên R: số lượng con đường (0 <= R <= 10000).
Tiếp theo là R dòng, mỗi dòng chứa hai số nguyên c1 và c2 cho biết một con đường nối giữa hai điểm giao cắt c1 và c2.

### Định dạng Đầu ra
Ghi ra file WALKING.OUT:
Với mỗi bộ test, in ra một dòng chứa văn bản Possible nếu Kamal có thể thực hiện được hành trình, ngược lại in ra Not Possible.

### Ví dụ
| Input | Output |
| :--- | :--- |
| 2 2 | Possible |
| 0 1 | |
| 1 0 | |
| 2 1 | Not Possible |
| 0 1 | |

### Subtasks
* Subtask 1 (40%): N <= 20, R <= 50.
* Subtask 2 (60%): N <= 200, R <= 10000.

✅ Đã AC: 1 / 1 submissions