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:

+ Dòng đầu tiên chứa hai số nguyên \(n,\ m\ (2\ \leq \ n\ \leq 100,\ 2 \leq \ m\ \leq \ 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.

+ \(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ả: 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ụ

Trong bộ test thư nhất: An đi làm như sau: \(\mathbf{1 \rightarrow}\ 3\ \mathbf{\rightarrow}\ 4\mathbf{\rightarrow 2 \rightarrow}6\mathbf{\rightarrow}3\mathbf{\rightarrow}4\mathbf{\rightarrow 5 \rightarrow 1}\)