Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QVESCAPE - Help Conan 9 !

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qvescape


Anh Quang Vũ dạo này khá hư hỏng, suốt ngày cứ chơi bời lêu lổng nên đã bị bạn Như Quỳnh trừng phạt. Nhưng bạn Như Quỳnh rất nương tay nên chỉ thử anh anh Quang Vũ bằng cách ném vào ngục tối bởi vua bóng tối để xác định độ ngoan của anh ta. Cái ngục được tạo dáng thành một hình lập phương với những bức tường đá lớn. Những căn phòng được nối bởi những lối đi nên vì vậy toàn bộ ngục tối khi nhìn từ phía trên trông giống như một đường xoắn ốc. Những căn phòng đc đánh số như sau:

... 15 14 13

5 4 3 12

6 1 2 11

7 8 9 10

Sau một trận động đất lớn một số bức tường đã bị phá hủy và những lối đi mới được hình thành giữa những phòng kế bên

Anh Quang Vũ đang ở phòng 1 . Ông ấy biết rằng lối thoát đc đặt ở phòng N, và muốn chạy thoát trong lúc mọi người đang hoảng loạn vì trận động đất, bởi vì vua bóng tối đang canh gác ngục tối, anh Quang Vũ muốn dùng con đường đi nhanh nhất để thoát khỏi ngục tối.

Viết chương trình đưa ra vị trí của lối thoát N và danh sách những lối đi mới, xác định số đoạn đường phải đi nhỏ nhất mà anh Quang Vũ phải đi qua trước khi thóat khỏi ngục.

Input:

Dòng đầu tiên của input chứa một số nguyên N(1<=N<=10^15), phòng mà lối thoát ở đó.

Dòng thứ hai chứa 1 số nguyên K (1<=K<=100000), số của con đường mới.

Mỗi dòng K chứa 1 số nguyên B(4<=B<=10^15) nghĩa là một con đường mới được nối vào hai phòng A,B cạnh nhau, nơi mà A

Output:

Output chứa 1 số nguyên, số con đường nhỏ nhất mà anh Quang Vũ phải đi qua trước khi thoát.

Nếu không thoát ra, anh Vũ sẽ bị tử ẹo tại hang động này, hy vọng các bạn sẽ giúp anh Vũ thoát khỏi hang.

P/S: 50% số test có N<=10^5

Ex:

Input

31
9
15
25
30
6
9
19
24
27
4

Output

6


Được gửi lên bởi:Phong
Ngày:2008-07-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 2007-2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.