Đất nước XAY xinh đẹp có n thành phố được đánh số từ 1 đến ~ n ~ và một hệ thống đường sắt gồm ~ m ~ tuyến đường sắt hai chiều. Vì là một đất nước vô cùng phát triển nên XAY đã xây thêm các tuyến đường bộ hai chiều giữa tất cả các cặp thành phố chưa có tuyến đường sắt. Mỗi tuyến đường sắt hay đường bộ đều đi mất đúng một tiếng đồng hồ. Để chuẩn bị cho trại hè Tin học 2018, Ming và Tuấn xuất phát cùng lúc từ thủ đô Thăng Long - thành phố 1, và đi đến thành phố Hạ Long - thành phố ~ n ~. Trong khi Tuấn di chuyển bằng xe bus thì Ming chọn tàu hỏa do sợ say xe (?). Xe bus chỉ có thể đi trên những tuyến đường bộ, còn tàu hỏa chỉ có thể đi trên những tuyến đường sắt. Cả xe bus và tàu hỏa đều không dừng lại cho đến khi về đến thành phố ~ n ~.

Mặc dù vô cùng phát triển nhưng hệ thống giao thông của XAY lại khá lộn xộn - nếu xe bus chở Tuấn và tàu hỏa chở Ming gặp nhau ở bất kì thành phố nào mà không phải 1 hay ~ n ~ thì có thể xảy ra va chạm. Do đó, ban tổ chức phải bố trí tuyến đường của cả 2 sao cho chúng không đi qua cùng một thành phố nào ngoài 1 và ~ n ~. Ngoài ra, Ban tổ chức cũng muốn Ming và Tuấn đến Hạ Long sớm nhất có thể. Hãy giúp Ban tổ chức nhé!

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~ n ~ ~(2 ≤ n ≤ 400) ~ và ~ m ~, số thành phố và số tuyến đường sắt của nước XAY.
• ~ m ~ dòng sau, mỗi dòng gồm hai số nguyên ~ u ~ và ~ v ~ ~ (1 ≤ u,v ≤ n) ~, thể hiện một tuyến đường sắt nối giữa ~ u ~ và ~ v ~.

Đề bài đảm bảo tồn tại nhiều nhất một tuyến đường sắt giữa 2 thành phố.

Kết quả

• Dòng duy nhất in ra thời gian nhỏ nhất để cả Ming và Tuấn có thể đến thành phố ~ n ~, hoặc -1 nếu Ming hoặc Tuấn không thể đến được.

Ví dụ:

Input 1

4 2
1 3
3 4 

Output 1

2 

Input 2

5 5
4 2
3 5
4 5
5 1
1 2 

Output 2

3