시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB5481458727.619%

문제

자카르타 시에는 N개의 큰 빌딩이 일직선 위에 위치하고 있다. 이들은 왼쪽부터 0, 1, ..., N - 1까지 번호가 붙어 있다. 자카르타에는 이들 말고 다른 큰빌딩은 없다.

자카르타에는 "도게"라고 불리는 신비한 생명체들이 살고 있다. 도게들은 0, 1, ..., M - 1 까지 번호가 붙어 있다. 도게 i는 최초에 빌딩 Bi에 위치하고 있다. 도게 i가 가진 신비한 힘은 그 능력치가 양의 정수 Pi로 표시된다. 도게는 이 신비한 힘으로 큰 빌딩들 간에 점프를 할 수 있다. 큰 빌딩 b에 있는 능력치가 p인 도게는 한번의 점프로 큰빌딩 b + p(0 ≤ b + p < N이라야 함) 혹은 큰빌딩 b - p(0 ≤ b - p < N이라야 함)로 이동할 수 있다.

도게 0이 가장 대단한 도게이며 모든 도게들의 지도자이다. 도게 0은 급한 소식이 있어 이 소식을 도게 1에게 전해야 한다. 물론 가장 빨리 소식이 전해지기를 바란다. 뉴스를 전해 들은 도게는 다음의 두가지 중 하나를 할 수 있다.

  • 다른 큰 빌딩으로 점프.
  • 현재 위치한 빌딩의 다른 도게에게 소식을 전달

도게들을 도와주는 프로그램을 작성해야 한다. 이 프로그램은 소식을 도게 1에게 전할 수 있는 최소한의 점프 횟수를 계산해야 한다. 만약 소식을 전달하는 것이 불가능한 경우라면 그것도 알아내야 한다.

입력

입력의 첫 줄에는 정수 NM이 주어진다. 이후 M개의 줄에는 두 자연수 BiPi가 주어진다.

  • 0 ≤ Bi < N
  • 1 ≤ N ≤ 30, 000
  • 1 ≤ Pi ≤ 30, 000
  • 2 ≤ M ≤ 30, 000

출력

출력은 단 한 줄이며, 최소의 점프 횟수라야 한다. 불가능한 경우 -1을 출력한다.

예제 입력 1

5 3
0 2
1 1
4 1

예제 출력 1

5

힌트

다음 경우가 5 번의 점프로 가능한 시나리오이다.

  • 도게 0이 큰빌딩 2로 점프, 또 큰빌딩 4로 점프 (2번 점프).
  • 도게 0이 소식을 도게 2에게 전함.
  • 도게 2가 큰빌딩 3으로 점프, 또 큰빌딩 2로 점프, 또 큰빌딩 1로 점프 (3번 점프).
  • 도게 2가 도게 1에게 소식을 전함.
W3sicHJvYmxlbV9pZCI6IjEwODQ3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzkwXHVjZTc0XHViOTc0XHVkMGMwXHVjNzU4IFx1YjljOFx1Y2M5Y1x1YjhlOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzkwXHVjZTc0XHViOTc0XHVkMGMwIFx1YzJkY1x1YzVkMFx1YjI5NCA8ZW0+TjxcL2VtPlx1YWMxY1x1Yzc1OCBcdWQwNzAgXHViZTRjXHViNTI5XHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNGU0XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCAwLCAxLCAuLi4sIDxlbT5OPFwvZW0+IC0gMVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzkwXHVjZTc0XHViOTc0XHVkMGMwXHVjNWQwXHViMjk0IFx1Yzc3NFx1YjRlNCBcdWI5ZDBcdWFjZTAgXHViMmU0XHViOTc4IFx1ZDA3MFx1YmU0Y1x1YjUyOVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1Y2U3NFx1Yjk3NFx1ZDBjMFx1YzVkMFx1YjI5NCAmcXVvdDtcdWIzYzRcdWFjOGMmcXVvdDtcdWI3N2NcdWFjZTAgXHViZDg4XHViOWFjXHViMjk0IFx1YzJlMFx1YmU0NFx1ZDU1YyBcdWMwZGRcdWJhODVcdWNjYjRcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVhYzhjXHViNGU0XHVjNzQwIDAsIDEsIC4uLiwgPGVtPk08XC9lbT4gLSAxIFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVhYzhjIDxlbT5pPFwvZW0+XHViMjk0IFx1Y2Q1Y1x1Y2QwOFx1YzVkMCBcdWJlNGNcdWI1MjkgPGVtPkI8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPlx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWFjOGMgPGVtPmk8XC9lbT5cdWFjMDAgXHVhYzAwXHVjOWM0IFx1YzJlMFx1YmU0NFx1ZDU1YyBcdWQ3OThcdWM3NDAgXHVhZGY4IFx1YjJhNVx1YjgyNVx1Y2U1OFx1YWMwMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IDxlbT5QPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj5cdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjXHViMmU0LiBcdWIzYzRcdWFjOGNcdWIyOTQgXHVjNzc0IFx1YzJlMFx1YmU0NFx1ZDU1YyBcdWQ3OThcdWM3M2NcdWI4NWMgXHVkMDcwIFx1YmU0Y1x1YjUyOVx1YjRlNCBcdWFjMDRcdWM1ZDAgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQwNzAgXHViZTRjXHViNTI5IDxlbT5iPFwvZW0+XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyYTVcdWI4MjVcdWNlNThcdWFjMDAgPGVtPnA8XC9lbT5cdWM3NzggXHViM2M0XHVhYzhjXHViMjk0IFx1ZDU1Y1x1YmM4OFx1Yzc1OCBcdWM4MTBcdWQ1MDRcdWI4NWMgXHVkMDcwXHViZTRjXHViNTI5IDxlbT5iPFwvZW0+ICsgPGVtPnA8XC9lbT4oMCAmbGU7IDxlbT5iPFwvZW0+ICsgPGVtPnA8XC9lbT4gJmx0OyA8ZW0+TjxcL2VtPlx1Yzc3NFx1Yjc3Y1x1YzU3YyBcdWQ1NjgpIFx1ZDYzOVx1Yzc0MCBcdWQwNzBcdWJlNGNcdWI1MjkgPGVtPmI8XC9lbT4gLSA8ZW0+cDxcL2VtPigwICZsZTsgPGVtPmI8XC9lbT4gLSA8ZW0+cDxcL2VtPiAmbHQ7IDxlbT5OPFwvZW0+XHVjNzc0XHViNzdjXHVjNTdjIFx1ZDU2OClcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YWM4YyAwXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWIzMDBcdWIyZThcdWQ1NWMgXHViM2M0XHVhYzhjXHVjNzc0XHViYTcwIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWFjOGNcdWI0ZTRcdWM3NTggXHVjOWMwXHViM2M0XHVjNzkwXHVjNzc0XHViMmU0LiBcdWIzYzRcdWFjOGMgMFx1Yzc0MCBcdWFlMDlcdWQ1NWMgXHVjMThjXHVjMmRkXHVjNzc0IFx1Yzc4OFx1YzViNCBcdWM3NzQgXHVjMThjXHVjMmRkXHVjNzQ0IFx1YjNjNFx1YWM4YyAxXHVjNWQwXHVhYzhjIFx1YzgwNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWFjMDBcdWM3YTUgXHViZTY4XHViOWFjIFx1YzE4Y1x1YzJkZFx1Yzc3NCBcdWM4MDRcdWQ1NzRcdWM5YzBcdWFlMzBcdWI5N2MgXHViYzE0XHViNzgwXHViMmU0LiBcdWIyNzRcdWMyYTRcdWI5N2MgXHVjODA0XHVkNTc0IFx1YjRlNFx1Yzc0MCBcdWIzYzRcdWFjOGNcdWIyOTQgXHViMmU0XHVjNzRjXHVjNzU4IFx1YjQ1MFx1YWMwMFx1YzljMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjJlNFx1Yjk3OCBcdWQwNzAgXHViZTRjXHViNTI5XHVjNzNjXHViODVjIFx1YzgxMFx1ZDUwNC48XC9saT5cclxuXHQ8bGk+XHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWJlNGNcdWI1MjlcdWM3NTggXHViMmU0XHViOTc4IFx1YjNjNFx1YWM4Y1x1YzVkMFx1YWM4YyBcdWMxOGNcdWMyZGRcdWM3NDQgXHVjODA0XHViMmVjPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViM2M0XHVhYzhjXHViNGU0XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWMxOGNcdWMyZGRcdWM3NDQgXHViM2M0XHVhYzhjIDFcdWM1ZDBcdWFjOGMgXHVjODA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzgxMFx1ZDUwNCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzE4Y1x1YzJkZFx1Yzc0NCBcdWM4MDRcdWIyZWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWI3N2NcdWJhNzQgXHVhZGY4XHVhYzgzXHViM2M0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggPGVtPk48XC9lbT5cdWFjZmMgPGVtPk08XC9lbT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgPGVtPk08XC9lbT5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMTggPGVtPkI8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPlx1YzY0MCA8ZW0+UDxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4wICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmx0OyBOPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMzAsIDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyAzMCwgMDAwPFwvbGk+XHJcblx0PGxpPjIgJmxlOyBNICZsZTsgMzAsIDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1YjJlOCBcdWQ1NWMgXHVjOTA0XHVjNzc0XHViYTcwLCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjODEwXHVkNTA0IFx1ZDY5Zlx1YzIxOFx1Yjc3Y1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjAgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIyZTRcdWM3NGMgXHVhY2JkXHVjNmIwXHVhYzAwIDUgXHViYzg4XHVjNzU4IFx1YzgxMFx1ZDUwNFx1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjNjNFx1YWM4YyAwXHVjNzc0IFx1ZDA3MFx1YmU0Y1x1YjUyOSAyXHViODVjIFx1YzgxMFx1ZDUwNCwgXHViNjEwIFx1ZDA3MFx1YmU0Y1x1YjUyOSA0XHViODVjIFx1YzgxMFx1ZDUwNCAoMlx1YmM4OCBcdWM4MTBcdWQ1MDQpLjxcL2xpPlxyXG5cdDxsaT5cdWIzYzRcdWFjOGMgMFx1Yzc3NCBcdWMxOGNcdWMyZGRcdWM3NDQgXHViM2M0XHVhYzhjIDJcdWM1ZDBcdWFjOGMgXHVjODA0XHVkNTY4LjxcL2xpPlxyXG5cdDxsaT5cdWIzYzRcdWFjOGMgMlx1YWMwMCBcdWQwNzBcdWJlNGNcdWI1MjkgM1x1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDQsIFx1YjYxMCBcdWQwNzBcdWJlNGNcdWI1MjkgMlx1Yjg1YyBcdWM4MTBcdWQ1MDQsIFx1YjYxMCBcdWQwNzBcdWJlNGNcdWI1MjkgMVx1Yjg1YyBcdWM4MTBcdWQ1MDQgKDNcdWJjODggXHVjODEwXHVkNTA0KS48XC9saT5cclxuXHQ8bGk+XHViM2M0XHVhYzhjIDJcdWFjMDAgXHViM2M0XHVhYzhjIDFcdWM1ZDBcdWFjOGMgXHVjMThjXHVjMmRkXHVjNzQ0IFx1YzgwNFx1ZDU2OC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA4NDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKYWthcnRhIFNreXNjcmFwZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY2l0eSBvZiBKYWthcnRhIGhhcyBOIHNreXNjcmFwZXJzIGxvY2F0ZWQgb24gYSBsaW5lLCBjb252ZW5pZW50bHkgbnVtYmVyZWQgMCB0aHJvdWdoIE4tMSBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZXJlIGFyZSBubyBvdGhlciBza3lzY3JhcGVycyBpbiBKYWthcnRhLjxcL3A+XHJcblxyXG48cD5KYWthcnRhIGlzIGluaGFiaXRlZCBieSBNIG15c3RpY2FsIGNyZWF0dXJlcyBjYWxsZWQgJnJkcXVvO2RvZ2UmcmRxdW87cy4gVGhlIGRvZ2VzIGFyZSBjb252ZW5pZW50bHkgbnVtYmVyZWQgMCB0aHJvdWdoIE0tMS4gRG9nZSBpIGluaXRpYWxseSByZXNpZGVzIGluIHNreXNjcmFwZXIgQjxzdWI+aTxcL3N1Yj4uIERvZ2UgaSBoYXMgYSBteXN0aWNhbCBwb3dlciwgcmVwcmVzZW50ZWQgd2l0aCBhIHBvc2l0aXZlIGludGVnZXIgUDxzdWI+aTxcL3N1Yj4uIFRoaXMgbXlzdGljYWwgcG93ZXIgZW5hYmxlcyBkb2dlcyB0byBqdW1wIGJldHdlZW4gc2t5c2NyYXBlcnMuIEluIGEgc2luZ2xlIGp1bXAsIGEgZG9nZSB3aXRoIHN1cGVycG93ZXIgcCB0aGF0IGlzIGN1cnJlbnRseSBpbiBza3lzY3JhcGVyIGIgY2FuIG1vdmUgdG8gZWl0aGVyIHNreXNjcmFwZXIgYitwIChpZiAwICZsZTsgYiArIHAgJmx0OyBOKSBvciBza3lzY3JhcGVyIGItcCAoaWYgMCAmbGU7IGIgJm1pbnVzOyBwICZsdDsgTikuPFwvcD5cclxuXHJcbjxwPkRvZ2UgMCBpcyB0aGUgbW9zdCBhd2Vzb21lIGRvZ2UsIGFuZCBpdCBpcyB0aGUgbGVhZGVyIG9mIGFsbCB0aGUgZG9nZXMuIEl0IGhhcyBhbiB1cmdlbnQgbmV3cyBmb3IgZG9nZSAxLCBhbmQgd2FudHMgdGhlIG5ld3MgdG8gcmVhY2ggZG9nZSAxIGFzIHF1aWNrbHkgYXMgcG9zc2libGUuIEFueSBkb2dlIHRoYXQgaGFzIHJlY2VpdmVkIHRoZSBuZXdzIGNhbiBkbyBhbnkgb2YgdGhlIGZvbGxvd2luZyBhY3Rpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk1ha2UgYSBqdW1wIHRvIG1vdmUgdG8gc29tZSBvdGhlciBza3lzY3JhcGVyLjxcL2xpPlxyXG5cdDxsaT5QYXNzIHRoZSBuZXdzIHRvIGFub3RoZXIgZG9nZSBpbiB0aGUgc2FtZSBza3lzY3JhcGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlBsZWFzZSBoZWxwIHRoZSBkb2dlcyBieSBjYWxjdWxhdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgdG90YWwganVtcHMgcmVxdWlyZWQgYnkgYWxsIGRvZ2VzIHRvIHBhc3MgdGhlIG5ld3MgdG8gZG9nZSAxLCBvciBpZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGRvIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0uIEVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgQjxzdWI+aTxcL3N1Yj4gYW5kIFA8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjAgJmxlOyBCPHN1Yj5pPFwvc3ViPiAmbHQ7IE48XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAzMCwgMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDMwLCAwMDA8XC9saT5cclxuXHQ8bGk+MiAmbGU7IE0gJmxlOyAzMCwgMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRvdGFsIGp1bXBzLCBvciAtMSBpZiBpdCBpcyBpbXBvc3NpYmxlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5IZXJlIGlzIG9uZSBvZiB0aGUgcG9zc2libGUgc2NlbmFyaW9zIHRvIHBhc3MgdGhlIG5ld3MgdXNpbmcgNSBqdW1wczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Eb2dlIDAganVtcHMgdG8gc2t5c2NyYXBlciAyIGFuZCB0aGVuIHRvIHNreXNjcmFwZXIgNCAoMiBqdW1wcykuPFwvbGk+XHJcblx0PGxpPkRvZ2UgMCBwYXNzZXMgdGhlIG5ld3MgdG8gZG9nZSAyLjxcL2xpPlxyXG5cdDxsaT5Eb2dlIDIganVtcHMgdG8gc2t5c2NyYXBlciAzLCBhbmQgdGhlbiB0byBza3lzY3JhcGVyIDIsIGFuZCB0aGVuIHRvIHNreXNjcmFwZXIgMSAoMyBqdW1wcykuPFwvbGk+XHJcblx0PGxpPkRvZ2UgMiBwYXNzZXMgdGhlIG5ld3MgdG8gZG9nZSAxLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d