Elearning CodePath – CTP Online Judge

COVID

---

### 📝 Bài toán
Trong tình hình bệnh dịch phức tạp hiện nay, để đảm bảo kiểm soát dịch, các thành phố đã lập ra các chốt kiểm tra. Bạn AN mỗi ngày đi làm và về nhà theo nguyên tắc một cung đường 2 điểm đến, đó là từ nhà đến cơ quan và sau đó lại quay về nhà.
Cho $N$ trạm kiểm tra và $M$ con đường một chiều nối giữa các trạm. Em hãy viết chương trình giúp bạn AN tìm một đường đi sao cho phải đi qua số trạm kiểm tra khác nhau là ít nhất.

### 📥 Dữ liệu vào
Từ tệp văn bản COVID.INP gồm:
+ Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 100, 2 \le M \le 200$), $N$ là số trạm kiểm soát được đánh số từ 1 tới $N$, $M$ là số tuyến đường nối giữa các trạm.
+ Trong $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $A, B$ là hướng của tuyến đường đi từ $A$ tới $B$.

### 📤 Kết quả
Ghi ra tệp văn bản COVID.OUT số trạm khác nhau ít nhất mà An phải đi qua khi đi làm từ nhà tới cơ quan và từ cơ quan về nhà.

### ⚠️ Chú ý
Nhà của bạn An là xuất phát từ trạm số 1 và cơ quan ở vị trí trạm số 2.

### ✨ Ví dụ
| COVID.INP | COVID.OUT | Giải thích |
| :--- | :--- | :--- |
| 6 7 1 3 3 4 4 5 5 1 4 2 2 6 6 3 | 6 | Trong ví dụ thứ nhất, An đi làm như sau: 1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4 -> 5 -> 1 |
| 9 11 1 3 3 4 4 2 2 5 5 3 3 6 6 1 2 7 7 8 8 9 9 1 | 6 | |

✅ Đã AC: 3 / 6 submissions