시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB257777.778%

문제

한 도시에 N개의 무선 통신 기지국이 있다. 각각의 기지국의 위치는 x, y 좌표로 표현되며 각 기지국의 좌표는 서로 다르다.

기지국에서는 특정 주파수의 전파를 이용하여 통신을 한다. 만약 두 기지국의 거리가 20을 넘지 않으면 두 기지국은 인접해 있다고 한다. 인접해 있는 두 기지국은 전파의 방해를 막기 위해 서로 다른 주파수를 사용해야 한다. 또한 주파수가 비슷할 경우 통신 장애가 발생할 수 있기 때문에, 2 이상 차이나야 한다고 하자. 편의상 주파수는 자연수만 고려하자.

무선 통신 기기를 만들 때에는 가능한 모든 주파수를 다 처리해 주어야 하기 때문에, 사용되는 주파수의 종류수가 적은 편이 유리하다.

무선 통신 기지국의 위치가 주어졌을 때, 사용되는 주파수의 최소 종류수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 12)이 주어진다. 다음 N개의 줄에는 각 기지국의 좌표가 실수로 주어진다. 입력으로 주어지는 기지국의 위치는 비교적 넓게 퍼져 있어서, 한 기지국에는 최대 4개(물론 자기 자신을 제외하고)의 기지국만 인접해 있다고 가정하자.

출력

첫째 줄에 주파수의 최소 종류수를 출력한다.

예제 입력 1

5
0 0
5 7.5
1 -3
10.75 -20.1
12.01 -22

예제 출력 1

3

예제 입력 2

6
0 1
19 0
38 1
38 21
19 22
0 21

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjIzNDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWMxMjAgXHVkMWI1XHVjMmUwIFx1YWUzMFx1YzljMFx1YWQ2ZCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgeCwgeSBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViYTcwIFx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzMFx1YzljMFx1YWQ2ZFx1YzVkMFx1YzExY1x1YjI5NCBcdWQyYjlcdWM4MTUgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1YzgwNFx1ZDMwY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVkMWI1XHVjMmUwXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjQ1MCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIDIwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViNDUwIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzQwIFx1YzgwNFx1ZDMwY1x1Yzc1OCBcdWJjMjlcdWQ1NzRcdWI5N2MgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjOGZjXHVkMzBjXHVjMjE4XHVhYzAwIFx1YmU0NFx1YzJiN1x1ZDU2MCBcdWFjYmRcdWM2YjAgXHVkMWI1XHVjMmUwIFx1YzdhNVx1YzU2MFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDIgXHVjNzc0XHVjMGMxIFx1Y2MyOFx1Yzc3NFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWQzYjhcdWM3NThcdWMwYzEgXHVjOGZjXHVkMzBjXHVjMjE4XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVhZTMwXHViOTdjIFx1YjljY1x1YjRlNCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM4ZmNcdWQzMGNcdWMyMThcdWI5N2MgXHViMmU0IFx1Y2M5OFx1YjlhY1x1ZDU3NCBcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGFjXHVjNmE5XHViNDE4XHViMjk0IFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yzc1OCBcdWM4ODVcdWI5NThcdWMyMThcdWFjMDAgXHVjODAxXHVjNzQwIFx1ZDNiOFx1Yzc3NCBcdWM3MjBcdWI5YWNcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4ODVcdWI5NThcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4oMSAmbGU7IE4gJmxlOyAxMilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjMmU0XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YmU0NFx1YWQ1MFx1YzgwMSBcdWIxMTNcdWFjOGMgXHVkMzdjXHVjODM4IFx1Yzc4OFx1YzViNFx1YzExYywgXHVkNTVjIFx1YWUzMFx1YzljMFx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgNFx1YWMxYyhcdWJiM2NcdWI4NjAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NThcdWFjZTApXHVjNzU4IFx1YWUzMFx1YzljMFx1YWQ2ZFx1YjljYyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVjODg1XHViOTU4XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzQ5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGhvbmUgSG9tZSIsImRlc2NyaXB0aW9uIjoiPHA+V2hlbiByZWxheSB0b3dlcnMgZm9yIG1vYmlsZSB0ZWxlcGhvbmVzIGNvbW11bmljYXRlIHdpdGggdGhlIG1vYmlsZSBwaG9uZXMgaW4gdGhlaXIgYXJlYSwgdGhlcmUgaXMgYWx3YXlzIHRoZSBwb3NzaWJpbGl0eSBvZiBpbnRlcmZlcmVuY2UuIFNvLCB3aGVuIGFzc2lnbmluZyB0aGUgdHJhbnNtaXNzaW9uIGZyZXF1ZW5jeSwgdGhlIEZDQyBtYWtlcyBzdXJlIHRoYXQgbmVhcmJ5IHRvd2VycyBoYXZlIGZyZXF1ZW5jaWVzIHRoYXQgYXJlbiYjMzk7dCB0b28gY2xvc2UuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGUgRkNDIGRvZXMgbm90IHdhbnQgdG8gYXNzaWduIHRvbyBtYW55IGRpZmZlcmVudCBmcmVxdWVuY2llczsgdGhleSB3YW50IHRvIHNhdmUgYXMgbWFueSBhcyBwb3NzaWJsZSBmb3Igb3RoZXIgdXNlcy4gWW91ciBqb2IgaXMgdG8gZmluZCBhbiBvcHRpbWFsIGFzc2lnbm1lbnQgb2YgZnJlcXVlbmNpZXMuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgdGhlIGZyZXF1ZW5jaWVzIHdpbGwgYmUgaW50ZWdlcnMuIE5lYXJieSB0b3dlcnMgbXVzdCBiZSBhc3NpZ25lZCBmcmVxdWVuY2llcyB0aGF0IGRpZmZlciBieSBhdCBsZWFzdCAyLiBZb3UmIzM5O2xsIGZpbmQgYW4gYXNzaWdubWVudCB1c2luZyBhcyBmZXcgZnJlcXVlbmNpZXMgYXMgcG9zc2libGUuIEZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgZm9sbG93aW5nIHR3byBhcnJhbmdlbWVudHMgb2YgdG93ZXJzLiBUd28gdG93ZXJzIG5lYXIgZWFjaCBvdGhlciBhcmUgaW5kaWNhdGVkIGJ5IHRoZSBjb25uZWN0aW5nIGxpbmUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGhvbmVob21lMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjdweDsgd2lkdGg6NTU3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSBmb2xsb3dpbmcgYXJlIGxlZ2FsIGZyZXF1ZW5jeSBhc3NpZ25tZW50cyB0byB0aGVzZSB0d28gdG93ZXIgY29uJm1hY3I7Z3VyYXRpb25zLiBIb3dldmVyLCB0aGUgc2Vjb25kIGFycmFuZ2VtZW50IGRvZXMgbm90IHVzZSB0aGUgZmV3ZXN0IG51bWJlciBvZiBmcmVxdWVuY2llcyBwb3NzaWJsZSwgc2luY2UgdGhlIHRvd2VyIHdpdGggZnJlcXVlbmN5IDUgY291bGQgaGF2ZSBmcmVxdWVuY3kgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waG9uZWhvbWUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzOXB4OyB3aWR0aDo1NzRweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBJbnB1dCBmb3IgZWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIHR3byBsaW5lczogdGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRoZSBpbnRlZ2VyIG4sIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0b3dlcnMuIFRoZSBuZXh0IGxpbmUgd2lsbCBiZSBvZiB0aGUgZm9ybSB4MSB5MSB4MiB5MiAuLi4geG4geW4gd2hlcmUgeGkgeWkgYXJlIHRoZSBjb29yZGluYXRlcyBvZiB0b3dlciBpLiBBIHBhaXIgb2YgdG93ZXJzIGFyZSBjb25zaWRlcmVkICZxdW90O25lYXImcXVvdDsgZWFjaCBvdGhlciBpZiB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGVtIGlzIG5vIG1vcmUgdGhhbiAyMC4gVGhlcmUgd2lsbCBiZSBubyBtb3JlIHRoYW4gMTIgdG93ZXJzIGFuZCBubyB0b3dlciB3aWxsIGhhdmUgbW9yZSB0aGFuIDQgdG93ZXJzIG5lYXIgaXQuIEEgdmFsdWUgb2YgbiA9IDAgaW5kaWNhdGVzIGVuZCBvZiBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdSBzaG91bGQgcHJpbnQgb25lIGxpbmUgaW4gdGhlIGZvcm1hdDo8XC9wPlxyXG5cclxuPHA+VGhlIHRvd2VycyBpbiBjYXNlIG4gY2FuIGJlIGNvdmVyZWQgaW4gZiBmcmVxdWVuY2llcy48XC9wPlxyXG5cclxuPHA+d2hlcmUgeW91IGRldGVybWluZSB0aGUgdmFsdWUgZm9yIGYuIFRoZSBjYXNlIG51bWJlcnMsIG4sIHdpbGwgc3RhcnQgYXQgMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d