Hai tuyến đường

Cho $n$ thành phố (đánh số từ $1$ đến $n$) và $m$ tuyến đường sắt hai chiều. Mạng đường bộ được định nghĩa rất đơn giản: với mỗi cặp thành phố khác nhau $x$ và $y$, tồn tại một con đường hai chiều giữa $x$ và $y$ khi và chỉ khi giữa $x$ và $y$ không có đường sắt.

Một con tàu và một chiếc xe buýt cùng xuất phát từ thành phố $1$ tại cùng một thời điểm. Cả hai đều có đích đến là thành phố $n$. Mỗi lần di chuyển từ một thành phố sang một thành phố lân cận (theo đúng một đường sắt hoặc một con đường) đều mất chính xác $1$ giờ. Tàu chỉ được đi trên đường sắt, xe buýt chỉ được đi trên đường bộ. Mỗi phương tiện có thể đi qua một cạnh nhiều lần.

Để tránh va chạm tại các điểm giao đường sắt, tàu và xe buýt không được có mặt ở cùng một thành phố nào (ngoại trừ thành phố $n$) cùng một lúc.

Hãy xác định khoảng thời gian nhỏ nhất sao cho cả hai phương tiện đều đã đến thành phố $n$, nghĩa là giá trị lớn nhất giữa thời điểm tàu đến và thời điểm xe buýt đến. Hai phương tiện được phép đến đích cùng lúc. Nếu có ít nhất một phương tiện không thể đến được thành phố $n$, hãy in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số thành phố và số đường sắt.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1\le u,v\le n$, $u\ne v$) cho biết có một đường sắt nối hai thành phố $u$ và $v$. Đảm bảo giữa mỗi cặp thành phố có nhiều nhất một đường sắt.

Dữ liệu ra

In ra một số nguyên — khoảng thời gian nhỏ nhất theo yêu cầu, hoặc $-1$ nếu không khả thi.

Ràng buộc

• $2\le n\le 400$
• $0\le m\le \frac{n(n-1)}{2}$

Ví dụ