Thành phố của Tý có \(N\) nút giao thông (được đánh số từ \(1\) đến \(N\)) và \(M\) con đường một chiều kết nối giữa chúng. Tý muốn đi xe máy từ nút giao \(1\) tới nút giao \(N\). Tuy nhiên, do hệ thống đường phân luồng một chiều chưa tối ưu nên có thể không tồn tại đường đi.

Để giải quyết vấn đề này, Tý được phép đảo ngược chiều một số con đường một chiều thành chiều ngược lại. Mỗi lần đảo ngược chiều của một con đường tốn chi phí \(1\).

Hãy giúp Tý tìm chi phí tối thiểu để tạo ra một lộ trình đi từ nút giao \(1\) đến nút giao \(N\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) mô tả một con đường một chiều từ nút giao \(u\) sang nút giao \(v\).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí tối thiểu (số cạnh cần đảo chiều ít nhất). Nếu không có cách nào kết nối, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4
1 2
2 3
4 3
1 4

Output:

1

(Giải thích ví dụ: Đảo chiều cạnh 4 -> 3 thành 3 -> 4, ta có lộ trình 1 -> 2 -> 3 -> 4).