Bình là một học sinh giỏi về Tin học, đặc biệt là lập trình. Để giúp con mình phát triển tư duy về lập trình, bố đã đưa ra cho em một bài toán như sau:

Cho một đồ thị có hướng gồm có \(n\) đỉnh được đánh số thứ tự từ \(1\) đến \(n\) , \(m\) cạnh được đánh số thứ tự từ \(1\) đến \(m\). Cạnh thứ \(i\) được cho bởi cặp số nguyên dương \(\left( x_{i},\ y_{i} \right)\) với ý nghĩa cạnh thứ \(i\) được nối trực tiếp giữa hai đỉnh và có hướng từ đỉnh \(x_{i}\) đến đỉnh \(y_{i}\).

Yêu cầu: Cho biết số lần ít nhất cần đảo ngược hướng của các cạnh so với hướng ban đầu để có được đường đi từ đỉnh \(1\) đến đỉnh \(n\).

Dữ liệu vào:

• Dòng đầu chứa 2 số nguyên dương \(n,\ m\ (1 \leq n,m \leq 10^{5})\) cách nhau một kí tự trắng;

• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa 2 số nguyên \(x_{i},\ y_{i}\ (1 \leq \ x_{i},\ y_{i} \leq n)\) (các số cách nhau một kí tự trắng) cho biết cạnh thứ \(i\) có hướng đi từ đỉnh \(x_{i}\) đến đỉnh \(y_{i}\).

Kết quả: Ghi ra một số nguyên duy nhất là đáp án của bài toán trong trường hợp không tìm được thì ghi -1.

Ví dụ:

Input	Output	Minh họa	Giải thích
7 7 1 6 2 6 6 3 5 2 7 4 7 5 4 3	2		Trong trường hợp cho phép đảo chiều thì đồ thị đã cho có 2 đường đi có thể là: (D1): 1-6-2-5-7 (D2): 1-6-3-4-7 Trong đó D1 cần 3 lần đảo hướng của cạnh, D2 cần 2 lần đảo hướng của cạnh. Vậy đáp án của bài toán là 2 (min(2, 3)=2).

Ràng buộc:

• 50% số test: \(1 \leq n,m \leq 4000\);

• 50% số test còn lại \(1 \leq n,m \leq 10^{5}\).