Bình được giao nhiệm vụ vận chuyển hàng hóa từ kho số \(1\) đến kho số \(N\) trong mạng lưới logistics gồm \(N\) kho hàng và \(M\) tuyến đường liên kết vô hướng giữa chúng.

Mỗi tuyến đường nối giữa hai kho hàng \(u\) và \(v\) có chi phí sử dụng phụ thuộc vào tính chẵn lẻ của hai kho đó:

• Nếu tổng số hiệu hai kho hàng là chẵn (\((u + v)\) chia hết cho \(2\)), Bình đi qua tuyến đường này không tốn phí (chi phí bằng \(0\)).
• Nếu tổng số hiệu hai kho hàng là lẻ (\((u + v)\) không chia hết cho \(2\)), Bình đi qua tuyến đường này tốn chi phí bằng \(1\).

Hãy giúp Bình tìm tổng chi phí tối thiểu để di chuyển từ kho \(1\) đến kho \(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ả tuyến đường vô hướng giữa kho \(u\) và kho \(v\).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí tối thiểu. Nếu không thể đi tới, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4
1 2
2 3
3 4
1 3

Output:

1