시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjZDljXHVhZDZjIE5cdWFjZmMgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NzQgXHViMDk4XHVjNWY0XHViNDE4XHViYTc0Jm5ic3A7XHViODVjXHViZTQ4XHVhY2JkXHVjNzc0IFx1YWMwMFx1YzdhNSZuYnNwO1x1YmU2MFx1Yjk3OCBcdWFlMzhcdWI4NWMgXHViMzU4XHVjODA0XHVjNzQ0IFx1ZDBjOFx1Y2Q5YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWFjNzBcdWNjZDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2M8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2Q5Y1x1YWQ2YyBcdWJjODhcdWQ2MzggXHVjODE1XHVjMjE4Jm5ic3A7TiAoMSAmbGU7Jm5ic3A7TiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGM4XHViODVjIFx1YzBkZFx1YWUzNCBcdWQxYjVcdWI4NWNcdWM3NzgmbmJzcDtcdWM4MTVcdWMyMTggSyAoMSAmbGU7Jm5ic3A7SyAmbGU7Jm5ic3A7MTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgS1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOCBCICg0ICZsZTsgQiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwmbmJzcDtcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDFiNVx1Yjg1Y1x1YWMwMCBcdWM3NzhcdWM4MTFcdWQ1NWMgQSwgQihBJmx0O0JcdWM3N2MgXHVhY2JkXHVjNmIwKSBcdWJjMjlcdWM3NDQgXHVjNzg3XHViMjk0XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWIyOTQgXHViYTg1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWM5YzBcdWI5Y2MsIFx1Yzc3NFx1YjI5NCBCXHVjNjQwIFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWM3NzRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgQlx1YWMwMCAyMFx1Yzc3NFx1YmE3NCwgQVx1YjI5NCA3XHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQpLiBcdWI2MTBcdWQ1NWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YjRlNFx1Yzc0MCBcdWM4MDhcdWIzMDBcdWI4NWMgQlx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1YzVjNlx1YjJlNCgyLDMsNSw3LDEwLDEzIFx1YjRmMSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI4NWNcdWJlNDhcdWFjYmRcdWM3NzQgXHViMzU4XHVjODA0XHVjNzQ0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQxYjVcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzc0IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM5YzBcdWM5YzQgXHVjNzc0XHVkNmM0XHVjNzU4IFx1YjM1OFx1YzgwNFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXNlcnVwbG9hZFwva2R5MzEyXC8yMDE2MDMyOFwvMzBhYTBlY2VkNmE2Yzk4MWFkNGIzNDQ5ODI1ODQzYTgucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmJmOFx1Yjk3NFx1Y2Y1NFx1YjI5NCAxLTQtMTUtMTQtMTMtMzAtMzFcdWM3NTggNlx1YWMxY1x1Yzc1OCZuYnNwO1x1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHViMzU4XHVjODA0XHVjNzQ0IFx1ZDBjOFx1Y2Q5YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUQU1OSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5CcmF2ZSBTaXIgUm9iaW4gaGFzIGJlZW4gdGhyb3duIGluIHRoZSBkdW5nZW9uIGJ5IHRoZSBldmlsIGtpbmcuIFRoZSBkdW5nZW9uIGNvbnNpc3RzIG9mIGFuIGluZmluaXRlIG51bWJlciBvZiBjdWJlLXNoYXBlZCByb29tcyB3aXRoIGJpZyBzdG9uZSB3YWxscy4gUm9vbXMgYXJlIGNvbm5lY3RlZCBieSBwYXNzYWdlcyBzbyB0aGF0IHRoZSBlbnRpcmUgZHVuZ2Vvbiwgd2hlbiB2aWV3ZWQgZnJvbSBhYm92ZSwgbG9va3MgbGlrZSBhIHNwaXJhbC4gVGhlIHJvb21zIGFyZSBudW1iZXJlZCBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1RBTU5JQ0EucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjExcHg7IHdpZHRoOjIzOHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFmdGVyIGEgYmlnIGVhcnRocXVha2Ugc29tZSBvZiB0aGUgd2FsbHMgY29sbGFwc2VkLCBhbmQgbmV3IHBhc3NhZ2VzIHdlcmUgZm9ybWVkIGJldHdlZW4gYWRqYWNlbnQgcm9vbXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNpciBSb2JpbiBpcyBpbml0aWFsbHkgaW4gcm9vbSAxLiBTaXIgUm9iaW4ga25vd3MgdGhhdCB0aGUgZXhpdCBmcm9tIHRoZSBkdW5nZW9uIGlzIGxvY2F0ZWQgaW4gcm9vbSBOLCBhbmQgd2FudHMgdG8gZXNjYXBlIHdoaWxlIGV2ZXJ5b25lIGlzIGRpc3RyYWN0ZWQgYnkgdGhlIGVhcnRocXVha2UuIEJlY2F1c2UgdGhlIGV2aWwgZHJhZ29uIGlzIGd1YXJkaW5nIHRoZSBkdW5nZW9uLCBTaXIgUm9iaW4gd2FudHMgdG8gdXNlIHRoZSBmYXN0ZXN0IHdheSBvdXQgb2YgdGhlIGR1bmdlb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgbG9jYXRpb24gb2YgdGhlIGV4aXQgTiBhbmQgdGhlIGxpc3Qgb2YgbmV3IHBhc3NhZ2VzLCBkZXRlcm1pbmVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgcGFzc2FnZXMgdGhhdCBTaXIgUm9iaW4gbXVzdCBnbyB0aHJvdWdoIGJlZm9yZSBoZSBjYW4gZXhpdCB0aGUgZHVuZ2Vvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+MTU8XC9zdXA+KSwgdGhlIHJvb20gaW4gd2hpY2ggdGhlIGV4aXQgaXMgbG9jYXRlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgSyAoMSAmbGU7IEsgJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBuZXcgcGFzc2FnZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIEIgKDQgJmxlOyBCICZsZTsgMTA8c3VwPjE1PFwvc3VwPiksIG1lYW5pbmcgdGhhdCBhIG5ldyBwYXNzYWdlIG5vdyBjb25uZWN0cyBhZGphY2VudCByb29tcyBBIGFuZCBCLCB3aGVyZSBBJmx0O0IuIFRoZSBudW1iZXIgQSBpcyBub3QgZ2l2ZW4gZXhwbGljaXRseSwgYnV0IGl0IGNhbiBiZSB1bmlxdWVseSBkZXRlcm1pbmVkIGZyb20gQiAoZm9yIGV4YW1wbGUsIGlmIEIgaXMgMjAsIHRoZW4gQSBtdXN0IGJlIDcpLiBBbHNvLCBzb21lIHJvb21zIGNhbiBuZXZlciBiZSByb29tIEIgKHJvb21zIDIsIDMsIDUsIDcsIDEwLCAxMyBldGMuKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgYSBzaW5nbGUgaW50ZWdlciwgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBwYXNzYWdlcyB0aGF0IFNpciBSb2JpbiBtdXN0IGdvIHRocm91Z2ggYmVmb3JlIGhlIGNhbiBleGl0IHRoZSBkdW5nZW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGlzIGlzIHRoZSBsYXlvdXQgb2YgdGhlIGR1bmdlb24gYWZ0ZXIgdGhlIGVhcnRocXVha2U6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvVEFNTklDQTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk3cHg7IHdpZHRoOjIyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1pcmtvIGNhbiB1c2UgdGhlIHJvdXRlIDEtNC0xNS0xNC0xMy0zMC0zMSwgdXNpbmcgb25seSA2IGhhbGx3YXlzIHRvIGV4aXQgdGhlIGR1bmdlb24uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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