시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB109363334.737%

문제

폴리큐브는 모서리의 길이가 1인 단위 정육면체를 면과 면끼리 붙여서 만든 입체이다. 아래 그림에서 왼쪽 아래 입체는 선과 선끼리 붙였기 때문에, 폴리큐브가 아니다.

폴리큐브를 이루는 정육면체의 중심은 모두 3차원 공간에 있고, 정수 좌표이다.

폴리큐브를 만들기 위해서 가장 처음 (0, 0, 0)에 있는 큐브부터 시작한다. 그 다음, 폴리큐브를 만드는 각 단계에서 다음 정육면체는 반드시 이전 정육면체와 면이 닿아야 한고, 지금까지 나오지 않은 정육면체이어야 한다. 예를 들어, 그림에서 왼쪽 위에 있는 폴리큐브는 아래와 같이 만들 수 있다.

(0,0,0) (0,0,1) (0,0,2) (0,0,3) (0,0,4)

그리고, 오른쪽 위에 있는 폴리큐브는 다음과 같이 만들 수 있다.

(0,0,0) (0,0,1) (0,1,1) (0,1,0) (1,0,0) (1,0,1) (1,1,1) (1,1,0)

폴리큐브는 단위 정육면체로 이루어져있기 때문에, 이것의 겉넓이은 모두 정수이다.

3차원 공간의 좌표가 주어질 때, 이것이 폴리큐브를 이루어지는지 구하고, 폴리큐브라면 겉넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에는 점의 개수 P(1 ≤ P ≤ 100)가 주어진다. 그 다음줄부터 정육면체의 중심 좌표가 차례대로 한 줄에 8개씩 주어진다.

입력으로 주어지는 좌표는 4보다 작거나 같은 음이 아닌 정수이다.

출력

각 테스트 케이스에 대해서 폴리큐브를 이룬다면 그것의 단면적을 출력하고, 아니라면 NO를 출력한 뒤에, 몇 번째 정육면체 폴리큐브를 이룰 수 없었는지를 출력한다. 첫 번째 정육면체는 1번이다.

예제 입력 1

4
5
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4
8
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1
4
0,0,0 0,0,1 1,1,0 1,1,1
20
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0
2,1,0 2,1,2 2,0,1 2,2,1

예제 출력 1

22
24
NO 3
72
W3sicHJvYmxlbV9pZCI6IjI3MDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWM3NTggXHVhYzg5XHViMTEzXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWIyOTQgXHViYWE4XHVjMTFjXHViOWFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWI5N2MgXHViYTc0XHVhY2ZjIFx1YmE3NFx1YjA3Y1x1YjlhYyBcdWJkOTlcdWM1ZWNcdWMxMWMgXHViOWNjXHViNGUwIFx1Yzc4NVx1Y2NiNFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Yzc4NVx1Y2NiNFx1YjI5NCBcdWMxMjBcdWFjZmMgXHVjMTIwXHViMDdjXHViOWFjIFx1YmQ5OVx1YzYwMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMDQlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDExXzA0XzQ3LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjQ2N3B4OyB3aWR0aDo1ODFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NDAgXHViYWE4XHViNDUwIDNcdWNjMjhcdWM2ZDAgXHVhY2Y1XHVhYzA0XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0YyAoMCwgMCwgMClcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDA1MFx1YmUwY1x1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NGMgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzRcdWM4MDQgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNjQwIFx1YmE3NFx1Yzc3NCBcdWIyZmZcdWM1NDRcdWM1N2MgXHVkNTVjXHVhY2UwLCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjNjdjXHVjYWJkIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPigwLDAsMCkgKDAsMCwxKSAoMCwwLDIpICgwLDAsMykgKDAsMCw0KTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4oMCwwLDApICgwLDAsMSkgKDAsMSwxKSAoMCwxLDApICgxLDAsMCkgKDEsMCwxKSAoMSwxLDEpICgxLDEsMCk8XC9wPlxyXG5cclxuPHA+XHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViMjk0IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0XHVhYzgzXHVjNzU4IFx1YWM4OVx1YjExM1x1Yzc3NFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4zXHVjYzI4XHVjNmQwIFx1YWNmNVx1YWMwNFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVjNzc0XHVhYzgzXHVjNzc0IFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWI3N2NcdWJhNzQgXHVhYzg5XHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmxlOyBUICZsZTsgMSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggUCgxICZsZTsgUCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjOTA0XHViZDgwXHVkMTMwIFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIDhcdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCA0XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjk3YyBcdWM3NzRcdWI4ZWNcdWIyZTRcdWJhNzQgXHVhZGY4XHVhYzgzXHVjNzU4IFx1YjJlOFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0XHVjNWQwLCBcdWJhODcgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNCBcdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWI5N2MgXHVjNzc0XHViOGYwIFx1YzIxOCBcdWM1YzZcdWM1YzhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1YjI5NCAxXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3MDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBcmVhIG9mIFBvbHljdWJlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBwb2x5Y3ViZSBpcyBhIHNvbGlkIG1hZGUgYnkgZ2x1aW5nIHRvZ2V0aGVyIHVuaXQgY3ViZXMgKG9uZSB1bml0IG9uIGVhY2ggZWRnZSkgb24gb25lIG9yIG1vcmUgZmFjZXMuIFRoZSBmaWd1cmUgaW4gdGhlIGxvd2VyLWxlZnQgaXMgbm90IGEgcG9seWN1YmUgYmVjYXVzZSBzb21lIGN1YmVzIGFyZSBhdHRhY2hlZCBhbG9uZyBhbiBlZGdlLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NjcmVlbiUyMFNob3QlMjAyMDEyLTEwLTA0JTIwYXQlMjAlRUMlOTglQTQlRUMlQTAlODQlMjAxMV8wNF80Ny5wbmdcIiBzdHlsZT1cImhlaWdodDo0NjdweDsgd2lkdGg6NTgxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgdGhlIHBvbHljdWJlIHdpbGwgYmUgZm9ybWVkIGZyb20gdW5pdCBjdWJlcyBjZW50ZXJlZCBhdCBpbnRlZ2VyIGxhdHRpY2UgcG9pbnRzIGluIDMtc3BhY2UuIFRoZSBwb2x5Y3ViZSB3aWxsIGJlIGJ1aWx0IHVwIG9uZSBjdWJlIGF0IGEgdGltZSwgc3RhcnRpbmcgd2l0aCBhIGN1YmUgY2VudGVyZWQgYXQgKDAsMCwwKS4gQXQgZWFjaCBzdGVwIG9mIHRoZSBwcm9jZXNzIChhZnRlciB0aGUgZmlyc3QgY3ViZSksIHRoZSBuZXh0IGN1YmUgbXVzdCBoYXZlIGEgZmFjZSBpbiBjb21tb24gd2l0aCBhIGN1YmUgcHJldmlvdXNseSBpbmNsdWRlZCBhbmQgbm90IGJlIHRoZSBzYW1lIGFzIGEgYmxvY2sgcHJldmlvdXNseSBpbmNsdWRlZC4gRm9yIGV4YW1wbGUsIGEgMS1ieS0xLWJ5LTUgYmxvY2sgKGFzIHNob3duIGFib3ZlIGluIHRoZSB1cHBlci1sZWZ0IHBvbHljdWJlKSBjb3VsZCBiZSBidWlsdCB1cCBhczo8XC9wPlxyXG5cclxuPHA+KDAsMCwwKSAoMCwwLDEpICgwLDAsMikgKDAsMCwzKSAoMCwwLDQpPFwvcD5cclxuXHJcbjxwPmFuZCBhIDItYnktMi1ieS0yIGN1YmUgKHVwcGVyLXJpZ2h0IGZpZ3VyZSkgY291bGQgYmUgYnVpbHQgYXM6PFwvcD5cclxuXHJcbjxwPigwLDAsMCkgKDAsMCwxKSAoMCwxLDEpICgwLDEsIDApICgxLDAsMCkgKDEsMCwxKSAoMSwxLDEpICgxLDEsIDApPFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoZSBzdXJmYWNlIG9mIHRoZSBwb2x5Y3ViZSBpcyBtYWRlIHVwIG9mIHVuaXQgc3F1YXJlcywgaXRzIGFyZWEgaXMgYW4gaW50ZWdlci48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIHRha2VzIGFzIGlucHV0IGEgc2VxdWVuY2Ugb2YgaW50ZWdlciBsYXR0aWNlIHBvaW50cyBpbiAzLXNwYWNlIGFuZCBkZXRlcm1pbmVzIHdoZXRoZXIgaXMgY29ycmVjdGx5IGZvcm1zIGEgcG9seWN1YmUgYW5kLCBpZiBzbywgd2hhdCB0aGUgc3VyZmFjZSBhcmVhIG9mIHRoZSBwb2x5Y3ViZSBpcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgbGluZXMgb2YgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgcG9pbnRzIFAsICgxICZsZTsgUCAmbGU7IDEwMCkgaW4gdGhlIHByb2JsZW0gaW5zdGFuY2UuIEVhY2ggc3VjY2VlZGluZyBsaW5lIGNvbnRhaW5zIHRoZSBjZW50ZXJzIG9mIHRoZSBjdWJlcywgZWlnaHQgdG8gYSBsaW5lIChleGNlcHQgcG9zc2libHkgZm9yIHRoZSBsYXN0IGxpbmUpLiBFYWNoIGNlbnRlciBpcyBnaXZlbiBhcyAzIG5vbi1uZWdhdGl2ZSBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IGNvbW1hcy4gVGhlIHBvaW50cyBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiZuYnNwO0FsbCBub24tbmVnYXRpdmUgaW50ZWdlcnMgd2lsbCBiZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgeW91IHNob3VsZCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciAoc3RhcnQgY291bnRpbmcgYXQgb25lKSwgYSBzcGFjZSBhbmQgdGhlIHN1cmZhY2UgYXJlYSBvZiB0aGUgcG9seWN1YmUgaWYgaXQgaXMgY29ycmVjdGx5IGZvcm1lZCwgT1IsIGlmIGl0IGlzIG5vdCBjb3JyZWN0bHkgZm9ybWVkLCB0aGUgc3RyaW5nICZsZHF1bztOTyZyZHF1bzsgYSBzcGFjZSBhbmQgdGhlIGluZGV4IChzdGFydGluZyB3aXRoIDEpIG9mIHRoZSBmaXJzdCBjdWJlIHdoaWNoIGRvZXMgbm90IHNoYXJlIGEgZmFjZSB3aXRoIGEgcHJldmlvdXMgY3ViZS4gTm90ZSB0aGF0IHRoZSBzdXJmYWNlIGFyZWEgaW5jbHVkZXMgdGhlIGFyZWEgb2YgYW55IGluY2x1ZGVkIGhvbGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Greater New York Region > 2008 Greater New York Programming Contest G번