An đang đứng ở tọa độ \(1\) trên một trục số dài gồm các điểm từ \(1\) đến \(N\). Tại vị trí \(x\) bất kỳ (\(1 \le x \le N\)), An có hai phương thức di chuyển:

1. Đi bộ sang điểm kế cạnh là \(x-1\) hoặc \(x+1\) (nếu điểm đích nằm trong đoạn từ \(1\) đến \(N\)). Chi phí của hành động này là \(1\).
2. Sử dụng cổng dịch chuyển nhanh một chiều. Hệ thống có \(K\) cổng dịch chuyển nhanh, cổng thứ \(i\) cho phép dịch chuyển trực tiếp từ \(u_i\) sang \(v_i\) với chi phí dịch chuyển là \(0\).

Hãy giúp An tìm chi phí tối thiểu để di chuyển từ điểm xuất phát \(1\) đến điểm đích \(N\).

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

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N, K \le 10^5\)).
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u_i, v_i\) (\(1 \le u_i, v_i \le N\)) mô tả một cổng dịch chuyển một chiều từ \(u_i\) sang \(v_i\).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí di chuyển tối thiểu.

Ràng buộc

Ví dụ

Input:

5 1
3 5

Output:

3