시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 451 166 132 38.938%

문제

블록은 아래와 같은 나무 조각 8개를 이용해서 하는 게임이다.

이 게임의 목표는 아래와 같은 조건을 지키면서 주어진 나무 조각을 이용해 가장 넓은 직사각형을 만드는 것이다.

  1. 가장 왼쪽 조각은 1번 조각, 가장 오른쪽 조각은 2번 조각이어야 한다.
  2. 인접한 조각은 서로 맞물려야 한다. 예를 들어, 4번 조각과 5번 조각은 항상 1번 조각의 오른쪽에 있어야 한다. 또, 4번 조각은 1번이나 3번조각의 오른쪽에 있을 수 있다.
  3. 1번 조각의 왼쪽과 2번 조각의 오른쪽에 맞물리는 조각은 없다.
  4. 각각의 1번 조각에 대해서, 대응하는 2번 조각이 있어야 하고, 5번 조각에 대해서도 대응하는 6번 조각이 있어야 한다.

예를 들어, 아래 2가지는 올바른 배치이다.

하지만, 아래 세 가지는 올바르지 않다.

세희는 이 게임을 앱으로 만들고 있다. 지금 구현할 부분은 사용자가 맞춘 블록이 문제의 조건에 올바른지 아닌지 판별하는 것이다.

한 사용자가 맞춘 블록 게임의 결과가 주어졌을 때, 올바른지 아닌지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 조각은 문제의 그림에 나와있는 숫자로 주어진다. 숫자는 공백없이 주어진다. 적어도 1개의 조각이 주어지며, 조각 10,000개를 넘기는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각각의 테스트 케이스에 대해서, 테스트 케이스 번호(1부터 시작)를 출력하고, 입력으로 주어진 배치가 올바르면 "VALID", 아니면 "NOT"을 출력한다.

예제 입력 1

142
1587862
132
143
0

예제 출력 1

1. VALID
2. VALID
3. NOT
4. NOT
W3sicHJvYmxlbV9pZCI6IjQ5MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHViZTE0XHViODVkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJlMTRcdWI4NWRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWIwOThcdWJiMzQgXHVjODcwXHVhYzAxIDhcdWFjMWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmxvY2sxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwNXB4OyB3aWR0aDo0NzJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjA5OFx1YmIzNCBcdWM4NzBcdWFjMDFcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM4NzBcdWFjMDFcdWM3NDAgMVx1YmM4OCBcdWM4NzBcdWFjMDEsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjODcwXHVhYzAxXHVjNzQwIDJcdWJjODggXHVjODcwXHVhYzAxXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc4XHVjODExXHVkNTVjIFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViOWRlXHViYjNjXHViODI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNFx1YmM4OCBcdWM4NzBcdWFjMDFcdWFjZmMgNVx1YmM4OCBcdWM4NzBcdWFjMDFcdWM3NDAgXHVkNTZkXHVjMGMxIDFcdWJjODggXHVjODcwXHVhYzAxXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIDRcdWJjODggXHVjODcwXHVhYzAxXHVjNzQwIDFcdWJjODhcdWM3NzRcdWIwOTggM1x1YmM4OFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjFcdWJjODggXHVjODcwXHVhYzAxXHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YWNmYyAyXHViYzg4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHViOWRlXHViYjNjXHViOWFjXHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMVx1YWMwMVx1Yzc1OCAxXHViYzg4IFx1Yzg3MFx1YWMwMVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjMwMFx1Yzc1MVx1ZDU1OFx1YjI5NCAyXHViYzg4IFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCA1XHViYzg4IFx1Yzg3MFx1YWMwMVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIzYzQgXHViMzAwXHVjNzUxXHVkNTU4XHViMjk0IDZcdWJjODggXHVjODcwXHVhYzAxXHVjNzc0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4IDJcdWFjMDBcdWM5YzBcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YmMzMFx1Y2U1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ibG9jazIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OThweDsgd2lkdGg6NTQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1NDRcdWI3OTggXHVjMTM4IFx1YWMwMFx1YzljMFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrMy5wbmdcIiBzdHlsZT1cImhlaWdodDo4NHB4OyB3aWR0aDo2MzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWQ3NmNcdWIyOTQgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM1NzFcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjOWMwXHVhZTA4IFx1YWQ2Y1x1ZDYwNFx1ZDU2MCBcdWJkODBcdWJkODRcdWM3NDAgXHVjMGFjXHVjNmE5XHVjNzkwXHVhYzAwIFx1YjlkZVx1Y2Q5OCBcdWJlMTRcdWI4NWRcdWM3NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWM2MmNcdWJjMTRcdWI5NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHViOWRlXHVjZDk4IFx1YmUxNFx1Yjg1ZCBcdWFjOGNcdWM3ODRcdWM3NTggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzYyY1x1YmMxNFx1Yjk3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWNcdWM3NTggXHVjODcwXHVhYzAxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjODcwXHVhYzAxIDEwLDAwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWFlMzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzgoMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTEpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJjMzBcdWNlNThcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc0XHViYTc0ICZxdW90O1ZBTElEJnF1b3Q7LCBcdWM1NDRcdWIyYzhcdWJhNzQgJnF1b3Q7Tk9UJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV29vZGVuIEJsb2NrcyIsImRlc2NyaXB0aW9uIjoiPHA+QmxvY2tzIGlzIGEgZ2FtZSB3aGVyZSB5b3UmcnNxdW87cmUgZ2l2ZW4gd29vZGVuIHBpZWNlcyB0aGF0IGNvbWUgaW4gZWlnaHQgc2hhcGVzIGFzIHNob3duIGJlbG93OjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDVweDsgd2lkdGg6NDcycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIG9iamVjdGl2ZSBvZiB0aGUgZ2FtZSBpcyB0byBhc3NlbWJsZSB0aGUgd2lkZXN0IHJlY3RhbmdsZSB0aGF0IGNhbiBiZSBtYWRlIG9mIGEgc3Vic2V0IG9mIHRoZSBnaXZlbiBwaWVjZXMgd2l0aCB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnM6PFwvcD5cclxuXHJcbjxwPlRoZSByZWN0YW5nbGUgbXVzdCBoYXZlIHNtb290aCBlZGdlcy4gSW4gb3RoZXIgd29yZHMsIHRoZSBsZWZ0LW1vc3QgcGllY2UgbXVzdCBiZSBwaWVjZSAjMSBhbmQgdGhlIHJpZ2h0LW1vc3QgcGllY2UgbXVzdCBiZSBwaWVjZSAjMi48YnIgXC8+XHJcbkFkamFjZW50IHBpZWNlcyBtdXN0IGludGVybG9jayBwcm9wZXJseS4gRm9yIGV4YW1wbGUsIGVpdGhlciBwaWVjZSAjNCBvciBwaWVjZSAjNSBtdXN0IGFwcGVhciB0byB0aGUgcmlnaHQgb2YgcGllY2UgIzEuIFNpbWlsYXJseSwgcGllY2UgIzQgY2FuIGFwcGVhciB0byB0aGUgcmlnaHQgb2YgcGllY2UgIzEgb3IgcGllY2UgIzMuPGJyIFwvPlxyXG5ObyBwaWVjZSBpbnRlcmxvY2tzIHRvIHRoZSBsZWZ0IG9mIHBpZWNlICMxLiBObyBwaWVjZSBpbnRlcmxvY2tzIHRvIHRoZSByaWdodCBvZiBwaWVjZSAjMi48YnIgXC8+XHJcbkZvciBlYWNoIHBpZWNlICMxLCB0aGUgcmVjdGFuZ2xlIG11c3QgaGF2ZSBhIG1hdGNoaW5nIHBpZWNlICMyLiBTaW1pbGFybHksIGZvciBlYWNoIHBpZWNlICM1LCB0aGVyZSBtdXN0IGJlIGEgbWF0Y2hpbmcgcGllY2UgIzYuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgZm9sbG93aW5nIHR3byBleGFtcGxlcyBhcmUgdmFsaWQgYXJyYW5nZW1lbnRzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrMi5wbmdcIiBzdHlsZT1cImhlaWdodDo5OHB4OyB3aWR0aDo1NDVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5XaGVyZWFzIHRoZSBmb2xsb3dpbmcgdGhyZWUgYXJlIG5vdDo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ibG9jazMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODRweDsgd2lkdGg6NjM2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBjb21wdXRlciBjb21wYW55IGlzIGludGVyZXN0ZWQgaW4gYnVpbGRpbmcgYSBCbG9ja3MgdmlkZW8gZ2FtZSBhbmQgaGFzIGhpcmVkIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIGlmIGEgZ2l2ZW4gcGllY2VzJnJzcXVvOyBhcnJhbmdlbWVudCBpcyB2YWxpZCBhY2NvcmRpbmcgdG8gdGhlIHJ1bGVzIGFib3ZlLCBvciBub3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgc3BlY2lcdWZiMDFlZCBvbiBhIHNlcGFyYXRlIGlucHV0IGxpbmUuIEVhY2ggcGllY2UgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyB0aGUgZGlnaXQgYXNzb2NpYXRlZCB3aXRoIGl0IGFzIGluIHRoZSBwcmV2aW91cyBcdWZiMDFndXJlLiBBbiBhcnJhbmdlbWVudCBpcyBzcGVjaVx1ZmIwMWVkIGJ5IGxpc3RpbmcgaXRzIGRpZ2l0cyB3aXRoIG5vIHNwYWNlcyBiZXR3ZWVuIHRoZSBkaWdpdHMuIEVhY2ggYXJyYW5nZW1lbnQgd2lsbCBoYXZlIGF0IGxlYXN0IG9uZSBwaWVjZSwgYnV0IG5vIG1vcmUgdGhhbiAxMCwwMDAgcGllY2VzLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIGluIHRoZSBpbnB1dCBcdWZiMDFsZSB3aWxsIGhhdmUgYSBzaW5nbGUgMC4gVGhhdCBsaW5lIGlzIG5vdCBwYXJ0IG9mIHRoZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSByZXN1bHQgb24gYSBzaW5nbGUgbGluZSB1c2luZyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHByZT5rLiByZXN1bHQ8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCAxLCkgYW5kIHJlc3VsdCBpcyAmcXVvdDtWQUxJRCZxdW90OyBpZiB0aGUgYXJyYW5nZW1lbnQgaXMgdmFsaWQsIG9yICZxdW90O05PVCZxdW90OyBpZiBpdCZyc3F1bztzIG5vdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=