시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 11 7 58.333%

문제

양의 정수 n이 주어질 때 N을 1부터 n까지의 정수의 집합이라 하자. N의 부분집합의 수열 A1, …, Ak이 아래의 성질을 만족할 때 완전히 다양화 되었다고(fully diversified) 한다.

a. 각각의 부분집합 Ai가 짝수 개의 원소로 이루어 졌다.

b. 어떤 N의 원소 m에 대해 m을 원소로 갖는 Ai가 m개 존재한다.

예를 들어 {1, 2, 3}의 부분집합으로 이뤄진 수열 {1, 3}, {2, 3}, {2, 3}은 완전히 다양화 된 수열이다. (수열의 항은 같을 수 있다)

N의 부분집합의 수열 중 완전히 다양화 된 수열은 여러 개가 존재하는데, 그 중 가장 짧은 것을 최소라 한다. 위의 예는 3이 세 개의 다른 집합에 나타나야 하므로, 위 수열이 최소이다.

정수 n이 주어졌을 때, 완전히 다양화된 수열이 있는가를 판별하고, 있다면 최소의 다양화된 수열을 찾아라.

입력

양의 정수 n이 한 줄에 하나씩 입력된다. 0이 입력되면 입력을 종료한다.

출력

집합 N에 대해 완전히 다양화 된 수열이 없다면 0을 출력하고 다음 줄에 빈 줄을 출력한다.

완전히 다양화 된 수열이 있다면, 수열의 길이를 출력하고 다음 줄에 집합을 출력한 뒤 다음 줄에 빈 줄을 출력한다.

각각의 원소는 오름차순으로 출력하여야 하며, 숫자들 사이에는 빈 칸을 하나씩 출력한다. 수열의 집합은 사전 순으로 출력하여야 한다. 각각의 문제에 대해 답은 여러 개가 있을 수 있다.

예제 입력 1

8
9
11
17
23
0

예제 출력 1

8
1 2 3 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
5 6 7 8
6 8
7 8
7 8

0

11
1 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
4 5 6 7 8 9 10 11
5 7 8 9 10 11
6 7 8 9 10 11
6 7 8 9 10 11
8 9 10 11
9 11
10 11
10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23
W3sicHJvYmxlbV9pZCI6IjI3NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NDRcdWM4MDRcdWQ3ODggXHViMmU0XHVjNTkxXHVkNjU0IFx1YjQxYyBcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIE5cdWM3NDQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiBOXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWMyMThcdWM1ZjQgQTxzdWI+MTxcL3N1Yj4sICZoZWxsaXA7LCBBPHN1Yj5rPFwvc3ViPlx1Yzc3NCBcdWM1NDRcdWI3OThcdWM3NTggXHVjMTMxXHVjOWM4XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YjJlNFx1YzU5MVx1ZDY1NCBcdWI0MThcdWM1YzhcdWIyZTRcdWFjZTAoZnVsbHkgZGl2ZXJzaWZpZWQpIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0YS4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OSBBPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM5ZGRcdWMyMTggXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjQgXHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRiLiBcdWM1YjRcdWI1YTQgTlx1Yzc1OCBcdWM2ZDBcdWMxOGMgbVx1YzVkMCBcdWIzMDBcdWQ1NzQgbVx1Yzc0NCBcdWM2ZDBcdWMxOGNcdWI4NWMgXHVhYzE2XHViMjk0IEE8c3ViPmk8XC9zdWI+XHVhYzAwIG1cdWFjMWMgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IHsxLCAyLCAzfVx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTA0XHVjOWM0IFx1YzIxOFx1YzVmNCB7MSwgM30sIHsyLCAzfSwgezIsIDN9XHVjNzQwIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTQgXHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC4gKFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NmRcdWM3NDAgXHVhYzE5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdE5cdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzU4IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YjJlNFx1YzU5MVx1ZDY1NCBcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWIyOTQgM1x1Yzc3NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YywgXHVjNzA0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWNkNWNcdWMxOGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTRcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YWMwMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWFjZTAsIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGNcdWM3NTggXHViMmU0XHVjNTkxXHVkNjU0XHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAwXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzlkMVx1ZDU2OSBOXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHViMmU0XHVjNTkxXHVkNjU0IFx1YjQxYyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTQgXHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjOWQxXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWI0YTQgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjMjJiXHVjNzkwXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDAgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYjM4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIyZjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVsbHkgRGl2ZXJzaWZpZWQgU2VxdWVuY2VzIG9mIFNldHMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciBuLCBsZXQgTiBiZSB0aGUgc2V0IG9mIGludGVnZXJzIGZyb20gMSB0byBuLiBBIGZpbml0ZSBzZXF1ZW5jZSBBMSwgJmhlbGxpcDssIEFrIG9mIHN1YnNldHMgb2YgTiBpcyBmdWxseSBkaXZlcnNpZmllZCBpZjo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FYWNoIHN1YnNldCBBaSBoYXMgYW4gZXZlbiBudW1iZXIgb2YgZWxlbWVudHMuPFwvbGk+XHJcblx0PGxpPkZvciBlYWNoIGVsZW1lbnQgbSBpbiBOLCB0aGVyZSBhcmUgZXhhY3RseSBtIHNldHMgQWkgaW4gdGhlIHNlcXVlbmNlIHdpdGggbSBhcyBhIG1lbWJlci48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIHNlcXVlbmNlIG9mIHN1YnNldHMgezEsM30sIHsyLDN9LCB7MiwzfSBpcyBhIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgezEsMiwzfS4gKE5vdGUgdGhhdCBzdWJzZXRzIGluIHRoZSBzZXF1ZW5jZSBtYXkgYmUgdGhlIHNhbWUuKTxcL3A+XHJcblxyXG48cD5BIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgTiBpcyBtaW5pbWFsIGlmIG5vIG90aGVyIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgTiBoYXMgYSBzbWFsbGVyIHNlcXVlbmNlIGNvdW50LiBUaGUgZXhhbXBsZSBhYm92ZSBpcyBtaW5pbWFsIHNpbmNlIHRoZSBlbGVtZW50IDMgbXVzdCBvY2N1ciBpbiAzIGRpZmZlcmVudCBzZXRzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0sIHdoaWNoLCBnaXZlbiBhbiBpbnRlZ2VyIG4sIGRldGVybWluZXMgd2hldGhlciB0aGVyZSBpcyBhIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgdGhlIGNvcnJlc3BvbmRpbmcgc2V0IE4gYW5kLCBpZiB0aGVyZSBpcyBhIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlLCBmaW5kcyBhIG1pbmltYWwgZnVsbHkgZGl2ZXJzaWZpZWQgc2VxdWVuY2Ugb2Ygc3Vic2V0cyBvZiBOLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgYmUgYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBuLCBvbmUgcGVyIGxpbmUgZm9sbG93ZWQgYnkgYSB6ZXJvICgwKSAob24gYW5vdGhlciBsaW5lKSBpbmRpY2F0aW5nIHRoZSBlbmQgb2YgdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZXJlIGlzIG5vIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgdGhlIGNvcnJlc3BvbmRpbmcgc2V0IE4sIG91dHB1dCBhIDAgb24gb25lIGxpbmUgZm9sbG93ZWQgYnkgYSBibGFuayBsaW5lLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBhIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgdGhlIGNvcnJlc3BvbmRpbmcgc2V0IE4sIG91dHB1dCB0aGUgbnVtYmVyIG9mIHNldHMgaW4geW91ciBtaW5pbWFsIHNlcXVlbmNlIG9uIG9uZSBsaW5lLCBmb2xsb3dlZCBieSB0aGUgc2V0cywgb25lIHBlciBsaW5lLCBmb2xsb3dlZCBieSBhIGJsYW5rIGxpbmUuPFwvcD5cclxuXHJcbjxwPlRoZSBlbGVtZW50cyBvZiBlYWNoIHNldCBzaG91bGQgYmUgb3V0cHV0IGluIGluY3JlYXNpbmcgb3JkZXIgd2l0aCBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIG51bWJlcnMuIFRoZSBzZXRzIG9mIHNlcXVlbmNlcyBzaG91bGQgYmUgb3V0cHV0IGluIGxleGljb2dyYXBoaWNhbCBvcmRlci4gVGhlcmUgbWF5IGJlIG1hbnkgcG9zc2libGUgc29sdXRpb25zIHRvIGVhY2ggcHJvYmxlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=