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\).

Ví dụ:

Giới hạn:

+ \(2 \leq m < n \leq 10^{5}\)

+ Các số \(u\) đôi một khác nhau