문제
Alice와 Bob은 N개의 정사각형을 일렬로 놓고 게임을 하고 있다. 정사각형에는 1부터 N까지의 수가 하나씩 적혀져 있다.
Alice와 Bob은 턴을 번갈아가면서 수를 하나씩 제거한다. 어떤 정사각형에 적혀있는 수를 제거하려면, 변을 공유하는 양쪽 정사각형에 더 큰 수가 있으면 안 된다. 수를 제거하면, 정사각형에는 수가 적혀있지 않은 상태가 된다.
1을 제거하는 사람이 게임을 승리한다. 게임의 초기 상태가 주어졌을 때, 두 사람이 최적의 방법으로 게임을 한다면, 누가 이기는지 구하는 프로그램을 작성하시오.
출력
각각의 테스트 케이스에 대해서, 게임을 승리하는 사람을 출력한다.
예제 출력 1
Bob
Alice
Bob
Alice
W3sicHJvYmxlbV9pZCI6IjEwNTYzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHVjMjE4IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL251bWJlcmdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6MzMzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QWxpY2VcdWM2NDAgQm9iXHVjNzQwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIxOTNcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzBcdWM3NTggXHVjMjE4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5BbGljZVx1YzY0MCBCb2JcdWM3NDAgXHVkMTM0XHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjgyNFx1YmE3NCwgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWNhYmQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YjM1NCBcdWQwNzAgXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWMyMThcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0LCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0XHViYTc0LCBcdWIyMDRcdWFjMDAgXHVjNzc0XHVhZTMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOICgxICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDU2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlciBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9udW1iZXJnYW1lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk0cHg7IHdpZHRoOjMzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFsaWNlIGFuZCBCb2IgYXJlIHBsYXlpbmcgYSBnYW1lIG9uIGEgbGluZSBvZiBOIHNxdWFyZXMuIFRoZSBsaW5lIGlzIGluaXRpYWxseSBwb3B1bGF0ZWQgd2l0aCBvbmUgb2YgZWFjaCBvZiB0aGUgbnVtYmVycyBmcm9tIDEgdG8gTi4gQWxpY2UgYW5kIEJvYiB0YWtlIHR1cm5zIHJlbW92aW5nIGEgc2luZ2xlIG51bWJlciBmcm9tIHRoZSBsaW5lLCBzdWJqZWN0IHRvIHRoZSByZXN0cmljdGlvbiB0aGF0IGEgbnVtYmVyIG1heSBvbmx5IGJlIHJlbW92ZWQgaWYgaXQgaXMgbm90IGJvcmRlcmVkIGJ5IGEgaGlnaGVyIG51bWJlciBvbiBlaXRoZXIgc2lkZS4gV2hlbiB0aGUgbnVtYmVyIGlzIHJlbW92ZWQsIHRoZSBzcXVhcmUgdGhhdCBjb250YWluZWQgaXQgaXMgbm93IGVtcHR5LiBUaGUgd2lubmVyIGlzIHRoZSBwbGF5ZXIgd2hvIHJlbW92ZXMgdGhlIDEgZnJvbSB0aGUgbGluZS4gR2l2ZW4gYW4gaW5pdGlhbCBjb25maWd1cmF0aW9uLCB3aG8gd2lsbCB3aW4sIGFzc3VtaW5nIEFsaWNlIGdvZXMgZmlyc3QgYW5kIGJvdGggb2YgdGhlbSBwbGF5IG9wdGltYWxseT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGJlZ2lucyB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgVCwgMSAmbGU7IFQgJmxlOyAxMDAsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDEwMCwgZGVub3RpbmcgdGhlIHNpemUgb2YgdGhlIGxpbmUuIE5leHQgaXMgYSBsaW5lIHdpdGggdGhlIG51bWJlcnMgZnJvbSAxIHRvIE4sIHNwYWNlIHNlcGFyYXRlZCwgZ2l2aW5nIHRoZSBudW1iZXJzIGluIGxpbmUgb3JkZXIgZnJvbSBsZWZ0IHRvIHJpZ2h0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG5hbWUgb2YgdGhlIHdpbm5pbmcgcGxheWVyIG9uIGEgc2luZ2xlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==