Một đồ thị có n đỉnh và m cạnh nối các đỉnh này, mỗi cạnh dài 1 km. Khả năng di chuyển của Minh rất kỳ lạ: mỗi giây cậu có thể chạy $2^t$ km, với t là một số tự nhiên bất kỳ. Hỏi Minh đi từ đỉnh 1 đến đỉnh n cần ít nhất bao nhiêu giây.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên n, m, biểu thị số đỉnh và số cạnh.

Tiếp theo là m dòng, mỗi dòng gồm hai số a, b, biểu thị một cạnh nối từ a đến b.

Dữ liệu ra

In ra một số nguyên biểu thị đáp án.

Ví dụ

Input

5 5
1 2
2 2
3 4
3 5
2 3

Output

1

Ghi chú

Phạm vi dữ liệu

$1 \le n \le 50$, $1 \le m \le 10000$, độ dài đường đi tối ưu ≤2^32^.