An vẽ trên giấy một hình vuông lớn và chia thành ~ m ~ ô vuông bên trong, các ô vuông được đánh số từ 1 đến ~ m ~. Ban đầu An có 1 viên đá ở ô 1, mỗi lần An tung xúc xắc và nhận được ~x~ điểm thì An được di chuyển viên đá lên đúng ~ x ~ ô (giả sử viên đá đang ở ô có giá trị ~ v ~, tung xúc xắc được ~ x ~ điểm thì viên đá được di chuyển lên ô ~ v+x ~). An nhận ra trò chơi này quá nhàm chán nên đã vẽ thêm ~ n ~ mũi tên, trong đó mỗi mũi tên có dạng ~ (u,v) ~ cho phép nếu viên sỏi đang ở ô có giá trị ~u~ thì ngay lập tức được chuyển đến ô có giá trị ~ v ~.

Hãy cho biết An cần ít nhất bao nhiêu lần tung xúc xắc để có thể di chuyển viên đá từ ô 1 đến ô ~ m ~. Biết rằng xúc xắc có 6 mặt được đánh số từ 1 đến 6 và có xác suất xuất hiện các mặt như nhau.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương ~ m, n ~
• ~ n ~ dòng tiếp theo mỗi dòng gồm 2 số ~ u,v ~ cho biết một mũi tên theo chiều từ ~ u ~ đến ~ v ~

Kết quả

Một số nguyên duy nhất cho biết số lần ít nhất An tung xúc xắc để di chuyển viên đá từ ô 1 đến ô ~ m ~.

Ràng buộc

• ~ 2 ≤ m < n ≤ 10^5 ~
• Các số ~u~ đôi một khác nhau

Ví dụ:

Input 1

100 10
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17 

Output 1

3