시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 112 31 23 28.750%

문제

용감한 로빈 경은 악마들의 왕에 의해 던전에 던져졌다. 던전은 거대한 바위벽들로 둘러쌓인 큐브모양으로 이루어져 있다. 던전 전제 방들은 통로로 연결되어있어서 위에서 본다면 나선형으로 생겼다. 방들의 번호는 다음과 같다.

거대한 지진 이후 몇개의 벽들이 무너졌고 새로운  통로들이 인접한 방들사이에 생성이 되었다.

로빈 경은 처음에 1번 방에 있다. 로빈경은 던전의 출구가 N방에 있다는 것을 알고 있고, 모두가 지진으로 산만해진 틈을 타서 탈출하고 싶어한다. 악룡이 던전을 지키고 있기 때문에 로빈 경은 가장 빠른 길을 통해서 던전을 탈출하고 싶어한다.

출구 N과 새로운 통로의 목록이 나열되면 로빈경이 가장 빠른 길로 던전을 탈출 하기 위해서 반드시 거쳐야 하는 통로의 수를 출력하는 프로그램을 만들어라

입력

첫번째 줄에는 출구 번호 정수 N (1 ≤ N ≤ 1015)이 주어진다.

두번째 줄에는 새로 생긴 통로인 정수 K (1 ≤ K ≤ 100,000)가 주어진다.

다음 K의 줄에는 하나의 정수 B (4 ≤ B ≤ 1015)가 주어지는데, 이는 새로운 통로가 인접한 A, B(A<B일 경우) 방을 잇는다는 것을 의미한다.

A는 명확하게 주어지지 않지만, 이는 B와 유일하게 이어질 수 있다. (예를 들어 B가 20이면, A는 7이 되어야만 한다). 또한 다른 방들은 절대로 B가 될 수 없다(2,3,5,7,10,13 등)

출력

로빈경이 던전을 탈출하기 위해 지나야 하는 통로의 수를 출력한다.

예제 입력 1

31
9
15
25
30
6
9
19
24
27
4

예제 출력 1

6

힌트

이 그림은 지진 이후의 던전의 모습을 나타낸 것이다.

미르코는 1-4-15-14-13-30-31의 6개의 경로를 이용하여 던전을 탈출 할 수 있다.

W3sicHJvYmxlbV9pZCI6IjI5NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWQ1NTggXHVhYzEwXHVjNjI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2YTlcdWFjMTBcdWQ1NWMgXHViODVjXHViZTQ4IFx1YWNiZFx1Yzc0MCBcdWM1NDVcdWI5YzhcdWI0ZTRcdWM3NTggXHVjNjU1XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWIzNThcdWM4MDRcdWM1ZDAgXHViMzU4XHVjODM4XHVjODRjXHViMmU0LiBcdWIzNThcdWM4MDRcdWM3NDAgXHVhYzcwXHViMzAwXHVkNTVjIFx1YmMxNFx1YzcwNFx1YmNiZFx1YjRlNFx1Yjg1YyBcdWI0NThcdWI3ZWNcdWMzMTNcdWM3NzggXHVkMDUwXHViZTBjXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjM1OFx1YzgwNCBcdWM4MDRcdWM4MWMgXHViYzI5XHViNGU0XHVjNzQwIFx1ZDFiNVx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM3ODhcdWM1YjRcdWMxMWMgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YmNmOFx1YjJlNFx1YmE3NCBcdWIwOThcdWMxMjBcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjMGRkXHVhY2JjXHViMmU0LiBcdWJjMjlcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VzZXJ1cGxvYWRcL2tkeTMxMlwvMjAxNjAzMjhcL2VjZDA1MzRjMzg3ODlmZWI3OTQ4YzI1NjhiNGFiNDM4LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjNzBcdWIzMDBcdWQ1NWMgXHVjOWMwXHVjOWM0IFx1Yzc3NFx1ZDZjNCBcdWJhODdcdWFjMWNcdWM3NTggXHViY2JkXHViNGU0XHVjNzc0IFx1YmIzNFx1YjEwOFx1Yzg0Y1x1YWNlMCBcdWMwYzhcdWI4NWNcdWM2YjQgJm5ic3A7XHVkMWI1XHViODVjXHViNGU0XHVjNzc0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjMjlcdWI0ZTRcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjMGRkXHVjMTMxXHVjNzc0IFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODVjXHViZTQ4IFx1YWNiZFx1Yzc0MCBcdWNjOThcdWM3NGNcdWM1ZDAgMVx1YmM4OCBcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWI4NWNcdWJlNDhcdWFjYmRcdWM3NDAgXHViMzU4XHVjODA0XHVjNzU4IFx1Y2Q5Y1x1YWQ2Y1x1YWMwMCBOXHViYzI5XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHViYWE4XHViNDUwXHVhYzAwIFx1YzljMFx1YzljNFx1YzczY1x1Yjg1YyBcdWMwYjBcdWI5Y2NcdWQ1NzRcdWM5YzQgXHVkMmM4XHVjNzQ0IFx1ZDBjMFx1YzExYyBcdWQwYzhcdWNkOWNcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiZuYnNwO1x1YzU0NVx1YjhlMVx1Yzc3NCBcdWIzNThcdWM4MDRcdWM3NDQgXHVjOWMwXHVkMGE0XHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViODVjXHViZTQ4IFx1YWNiZFx1Yzc0MCBcdWFjMDBcdWM3YTUmbmJzcDtcdWJlNjBcdWI5NzggXHVhZTM4XHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWIzNThcdWM4MDRcdWM3NDQgXHVkMGM4XHVjZDljXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDljXHVhZDZjIE5cdWFjZmMgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NzQgXHViMDk4XHVjNWY0XHViNDE4XHViYTc0Jm5ic3A7XHViODVjXHViZTQ4XHVhY2JkXHVjNzc0IFx1YWMwMFx1YzdhNSZuYnNwO1x1YmU2MFx1Yjk3OCBcdWFlMzhcdWI4NWMgXHViMzU4XHVjODA0XHVjNzQ0IFx1ZDBjOFx1Y2Q5YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWFjNzBcdWNjZDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2M8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDljXHVhZDZjIFx1YmM4OFx1ZDYzOCBcdWM4MTVcdWMyMTgmbmJzcDtOICgxICZsZTsmbmJzcDtOICZsZTsgMTA8c3VwPjE1PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjOFx1Yjg1YyBcdWMwZGRcdWFlMzQgXHVkMWI1XHViODVjXHVjNzc4Jm5ic3A7XHVjODE1XHVjMjE4IEsgKDEgJmxlOyZuYnNwO0sgJmxlOyZuYnNwOzEwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEtcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMTggQiAoNCAmbGU7IEIgJmxlOyAxMDxzdXA+MTU8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsJm5ic3A7XHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQxYjVcdWI4NWNcdWFjMDAgXHVjNzc4XHVjODExXHVkNTVjIEEsIEIoQSZsdDtCXHVjNzdjIFx1YWNiZFx1YzZiMCkgXHViYzI5XHVjNzQ0IFx1Yzc4N1x1YjI5NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5BXHViMjk0IFx1YmE4NVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHVjOWMwXHViOWNjLCBcdWM3NzRcdWIyOTQgQlx1YzY0MCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVjNzc0XHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IEJcdWFjMDAgMjBcdWM3NzRcdWJhNzQsIEFcdWIyOTQgN1x1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2NcdWI5Y2MgXHVkNTVjXHViMmU0KS4gXHViNjEwXHVkNTVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWI0ZTRcdWM3NDAgXHVjODA4XHViMzAwXHViODVjIEJcdWFjMDAgXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQoMiwzLDUsNywxMCwxMyBcdWI0ZjEpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViODVjXHViZTQ4XHVhY2JkXHVjNzc0IFx1YjM1OFx1YzgwNFx1Yzc0NCBcdWQwYzhcdWNkOWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkMWI1XHViODVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc3NCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjOWMwXHVjOWM0IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWIzNThcdWM4MDRcdWM3NTggXHViYWE4XHVjMmI1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VzZXJ1cGxvYWRcL2tkeTMxMlwvMjAxNjAzMjhcLzMwYWEwZWNlZDZhNmM5ODFhZDRiMzQ0OTgyNTg0M2E4LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJiZjhcdWI5NzRcdWNmNTRcdWIyOTQgMS00LTE1LTE0LTEzLTMwLTMxXHVjNzU4IDZcdWFjMWNcdWM3NTgmbmJzcDtcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YjM1OFx1YzgwNFx1Yzc0NCBcdWQwYzhcdWNkOWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVEFNTklDQSIsImRlc2NyaXB0aW9uIjoiPHA+QnJhdmUgU2lyIFJvYmluIGhhcyBiZWVuIHRocm93biBpbiB0aGUgZHVuZ2VvbiBieSB0aGUgZXZpbCBraW5nLiBUaGUgZHVuZ2VvbiBjb25zaXN0cyBvZiBhbiBpbmZpbml0ZSBudW1iZXIgb2YgY3ViZS1zaGFwZWQgcm9vbXMgd2l0aCBiaWcgc3RvbmUgd2FsbHMuIFJvb21zIGFyZSBjb25uZWN0ZWQgYnkgcGFzc2FnZXMgc28gdGhhdCB0aGUgZW50aXJlIGR1bmdlb24sIHdoZW4gdmlld2VkIGZyb20gYWJvdmUsIGxvb2tzIGxpa2UgYSBzcGlyYWwuIFRoZSByb29tcyBhcmUgbnVtYmVyZWQgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9UQU1OSUNBLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxMXB4OyB3aWR0aDoyMzhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BZnRlciBhIGJpZyBlYXJ0aHF1YWtlIHNvbWUgb2YgdGhlIHdhbGxzIGNvbGxhcHNlZCwgYW5kIG5ldyBwYXNzYWdlcyB3ZXJlIGZvcm1lZCBiZXR3ZWVuIGFkamFjZW50IHJvb21zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaXIgUm9iaW4gaXMgaW5pdGlhbGx5IGluIHJvb20gMS4gU2lyIFJvYmluIGtub3dzIHRoYXQgdGhlIGV4aXQgZnJvbSB0aGUgZHVuZ2VvbiBpcyBsb2NhdGVkIGluIHJvb20gTiwgYW5kIHdhbnRzIHRvIGVzY2FwZSB3aGlsZSBldmVyeW9uZSBpcyBkaXN0cmFjdGVkIGJ5IHRoZSBlYXJ0aHF1YWtlLiBCZWNhdXNlIHRoZSBldmlsIGRyYWdvbiBpcyBndWFyZGluZyB0aGUgZHVuZ2VvbiwgU2lyIFJvYmluIHdhbnRzIHRvIHVzZSB0aGUgZmFzdGVzdCB3YXkgb3V0IG9mIHRoZSBkdW5nZW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGxvY2F0aW9uIG9mIHRoZSBleGl0IE4gYW5kIHRoZSBsaXN0IG9mIG5ldyBwYXNzYWdlcywgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHBhc3NhZ2VzIHRoYXQgU2lyIFJvYmluIG11c3QgZ28gdGhyb3VnaCBiZWZvcmUgaGUgY2FuIGV4aXQgdGhlIGR1bmdlb24uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjE1PFwvc3VwPiksIHRoZSByb29tIGluIHdoaWNoIHRoZSBleGl0IGlzIGxvY2F0ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIEsgKDEgJmxlOyBLICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgbmV3IHBhc3NhZ2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgSyBsaW5lcyBjb250YWlucyBvbmUgaW50ZWdlciBCICg0ICZsZTsgQiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pLCBtZWFuaW5nIHRoYXQgYSBuZXcgcGFzc2FnZSBub3cgY29ubmVjdHMgYWRqYWNlbnQgcm9vbXMgQSBhbmQgQiwgd2hlcmUgQSZsdDtCLiBUaGUgbnVtYmVyIEEgaXMgbm90IGdpdmVuIGV4cGxpY2l0bHksIGJ1dCBpdCBjYW4gYmUgdW5pcXVlbHkgZGV0ZXJtaW5lZCBmcm9tIEIgKGZvciBleGFtcGxlLCBpZiBCIGlzIDIwLCB0aGVuIEEgbXVzdCBiZSA3KS4gQWxzbywgc29tZSByb29tcyBjYW4gbmV2ZXIgYmUgcm9vbSBCIChyb29tcyAyLCAzLCA1LCA3LCAxMCwgMTMgZXRjLikuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGEgc2luZ2xlIGludGVnZXIsIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgcGFzc2FnZXMgdGhhdCBTaXIgUm9iaW4gbXVzdCBnbyB0aHJvdWdoIGJlZm9yZSBoZSBjYW4gZXhpdCB0aGUgZHVuZ2Vvbi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhpcyBpcyB0aGUgbGF5b3V0IG9mIHRoZSBkdW5nZW9uIGFmdGVyIHRoZSBlYXJ0aHF1YWtlOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1RBTU5JQ0EyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5N3B4OyB3aWR0aDoyMjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NaXJrbyBjYW4gdXNlIHRoZSByb3V0ZSAxLTQtMTUtMTQtMTMtMzAtMzEsIHVzaW5nIG9ubHkgNiBoYWxsd2F5cyB0byBleGl0IHRoZSBkdW5nZW9uLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2008 > Croatian Olympiad in Informatics 2008 3번