문제
때는 2123년, UDPC는 전세계의 많은 지역을 아우르는 거대한 대회로 자라났다. UDPC를 구성하는 $N$개의 지역은 UDPC의 100주년을 맞아 모든 지역을 통일해 연합을 구성하기로 했다. 각 지역은 1ドル$부터 $N$까지의 지역 번호로 구분된다. 하지만 통일 과정에서 사소한 문제가 발생하는데, 바로 지역마다 지역 코드가 제각각이라는 점이다.
지역 코드는 지역 번호와 다른 것으로, 각 지역에 배정된 0ドル$부터 9ドル$까지의 숫자로 이루어진 문자열이다. 긴 회의 끝에, 다음과 같은 규칙을 통해 새 연합의 지역 코드를 결정하기로 하였다.
- 새 지역 코드는 기존 지역의 지역 코드 중 하나 이상을 골라 합친 뒤 문자 단위로 재배열한 것이어야 한다.
- 새 지역 코드는 외우기 쉽도록 회문이어야 한다. 회문이란, 왼쪽에서 오른쪽으로 읽은 것과 오른쪽에서 왼쪽으로 읽은 것이 서로 같은 문자열을 말한다.
- 새 지역 코드는 위의 조건을 만족하는 것 중 가장 짧은 것이다.
UDPC의 평화를 위해, 새 연합의 지역 코드를 구해 보자.
출력
첫째 줄에 새 지역 코드의 길이를 출력한다. 만약 새 지역 코드를 만드는 것이 불가능할 경우 -1을 출력한다.
새 지역 코드를 만드는 것이 가능할 경우 아래와 같이 두 줄을 더 출력한다.
둘째 줄에 새 지역 코드를 이루는 지역의 수 $M$을 출력한다.
셋째 줄에 새 지역 코드를 이루는 $M$개 지역의 지역 번호를 공백으로 구분해 오름차순으로 출력한다.
가능한 방법이 여러 가지일 경우 그중 아무 것이나 출력한다.
W3sicHJvYmxlbV9pZCI6IjMzNjk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOWMwXHVjNWVkIFx1Y2Y1NFx1YjRkYyBcdWM4MTVcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjU0Y1x1YjI5NCAyMTIzXHViMTQ0LCBVRFBDXHViMjk0IFx1YzgwNFx1YzEzOFx1YWNjNFx1Yzc1OCBcdWI5Y2VcdWM3NDAgXHVjOWMwXHVjNWVkXHVjNzQ0IFx1YzU0NFx1YzZiMFx1Yjk3NFx1YjI5NCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMzAwXHVkNjhjXHViODVjIFx1Yzc5MFx1Yjc3Y1x1YjBhY1x1YjJlNC4gVURQQ1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzljMFx1YzVlZFx1Yzc0MCBVRFBDXHVjNzU4IDEwMFx1YzhmY1x1YjE0NFx1Yzc0NCBcdWI5ZGVcdWM1NDQgXHViYWE4XHViNGUwIFx1YzljMFx1YzVlZFx1Yzc0NCBcdWQxYjVcdWM3N2NcdWQ1NzQgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YWMwMSBcdWM5YzBcdWM1ZWRcdWM3NDAgJDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMFx1Yzc1OCA8c3Ryb25nPlx1YzljMFx1YzVlZCBcdWJjODhcdWQ2Mzg8XC9zdHJvbmc+XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDFiNVx1Yzc3YyBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjMThjXHVkNTVjIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YmMxNFx1Yjg1YyBcdWM5YzBcdWM1ZWRcdWI5YzhcdWIyZTQgPHN0cm9uZz5cdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjPFwvc3Ryb25nPlx1YWMwMCBcdWM4MWNcdWFjMDFcdWFjMDFcdWM3NzRcdWI3N2NcdWIyOTQgXHVjODEwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YzljMFx1YzVlZCBcdWNmNTRcdWI0ZGM8XC9zdHJvbmc+XHViMjk0IDxzdHJvbmc+XHVjOWMwXHVjNWVkIFx1YmM4OFx1ZDYzODxcL3N0cm9uZz5cdWM2NDAgXHViMmU0XHViOTc4IFx1YWM4M1x1YzczY1x1Yjg1YywgXHVhYzAxIFx1YzljMFx1YzVlZFx1YzVkMCBcdWJjMzBcdWM4MTVcdWI0MWMgJDAkXHViZDgwXHVkMTMwICQ5JFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVhZTM0IFx1ZDY4Y1x1Yzc1OCBcdWIwNWRcdWM1ZDAsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWMwYzggXHVjNWYwXHVkNTY5XHVjNzU4IFx1YzljMFx1YzVlZCBcdWNmNTRcdWI0ZGNcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMwYzggXHVjOWMwXHVjNWVkIFx1Y2Y1NFx1YjRkY1x1YjI5NCBcdWFlMzBcdWM4NzQgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YzljMFx1YzVlZCBcdWNmNTRcdWI0ZGMgXHVjOTExIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NDQgXHVhY2U4XHViNzdjIFx1ZDU2OVx1Y2U1YyBcdWI0YTQgXHViYjM4XHVjNzkwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM3YWNcdWJjMzBcdWM1ZjRcdWQ1NWMgXHVhYzgzXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMGM4IFx1YzljMFx1YzVlZCBcdWNmNTRcdWI0ZGNcdWIyOTQgXHVjNjc4XHVjNmIwXHVhZTMwIFx1YzI3ZFx1YjNjNFx1Yjg1ZCA8c3Ryb25nPlx1ZDY4Y1x1YmIzODxcL3N0cm9uZz5cdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ2OGNcdWJiMzhcdWM3NzRcdWI3ODAsIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzdkXHVjNzQwIFx1YWM4M1x1YWNmYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3ZFx1Yzc0MCBcdWFjODNcdWM3NzQgXHVjMTFjXHViODVjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMwYzggXHVjOWMwXHVjNWVkIFx1Y2Y1NFx1YjRkY1x1YjI5NCBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjODMgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlVEUENcdWM3NTggXHVkM2M5XHVkNjU0XHViOTdjIFx1YzcwNFx1ZDU3NCwgXHVjMGM4IFx1YzVmMFx1ZDU2OVx1Yzc1OCBcdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjXHViOTdjIFx1YWQ2Y1x1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzljMFx1YzVlZFx1Yzc1OCBcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZSBOXFxsZSAxMF42KSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHVjOTExICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4IFx1YzljMFx1YzVlZFx1Yzc1OCBcdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJlNDRcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFNfaSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwICQwJFx1YmQ4MFx1ZDEzMCAkOSRcdWFlNGNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0MCAkMlxcdGltZXMgMTBeNiQgXHVjNzc0XHVkNTU4XHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjOCBcdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMwYzggXHVjOWMwXHVjNWVkIFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU2MCBcdWFjYmRcdWM2YjAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjOCBcdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTYwIFx1YWNiZFx1YzZiMCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YjQ1MCBcdWM5MDRcdWM3NDQgXHViMzU0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzggXHVjOWMwXHVjNWVkIFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YzIxOCAkTSRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjOCBcdWM5YzBcdWM1ZWQgXHVjZjU0XHViNGRjXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCAkTSRcdWFjMWMgXHVjOWMwXHVjNWVkXHVjNzU4IDxzdHJvbmc+XHVjOWMwXHVjNWVkIFx1YmM4OFx1ZDYzODxcL3N0cm9uZz5cdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3N2MgXHVhY2JkXHVjNmIwIFx1YWRmOFx1YzkxMSBcdWM1NDRcdWJiMzQgXHVhYzgzXHVjNzc0XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMzY5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlZ2lvbiBDb2RlIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgeWVhciAyMTIzLCBVRFBDIGhhcyBncm93biBpbnRvIGEgbWFzc2l2ZSBjb21wZXRpdGlvbiBzcGFubmluZyBtYW55IHJlZ2lvbnMgd29ybGR3aWRlLiBUbyBjZWxlYnJhdGUgdGhlIDEwMHRoIGFubml2ZXJzYXJ5IG9mIFVEUEMsIHRoZSAkTiQgcmVnaW9ucyB0aGF0IG1ha2UgdXAgVURQQyBoYXZlIGRlY2lkZWQgdG8gdW5pdGUgaW50byBhIHNpbmdsZSBmZWRlcmF0aW9uLiBFYWNoIHJlZ2lvbiBpcyBpZGVudGlmaWVkIGJ5IGEgPHN0cm9uZz5yZWdpb24gbnVtYmVyPFwvc3Ryb25nPiByYW5naW5nIGZyb20gJDEkIHRvICROJC4gSG93ZXZlciwgYSBtaW5vciBpc3N1ZSBoYXMgYXJpc2VuIGR1cmluZyB0aGUgdW5pZmljYXRpb24gcHJvY2VzczogdGhlIGZhY3QgdGhhdCZuYnNwOzxzdHJvbmc+cmVnaW9uIGNvZGVzPFwvc3Ryb25nPiB2YXJ5IGJ5IHJlZ2lvbi48XC9wPlxyXG5cclxuPHA+QSA8c3Ryb25nPnJlZ2lvbiBjb2RlPFwvc3Ryb25nPiBpcyBkaXN0aW5jdCBmcm9tIGEgPHN0cm9uZz5yZWdpb24gbnVtYmVyPFwvc3Ryb25nPjsgaXQgaXMgYSBzdHJpbmcgY29uc2lzdGluZyBvZiBkaWdpdHMgZnJvbSAkMCQgdG8gJDkkIGFzc2lnbmVkIHRvIGVhY2ggcmVnaW9uLiBBZnRlciBhIGxvbmcgZGlzY3Vzc2lvbiwgdGhlIGZvbGxvd2luZyBydWxlcyB3ZXJlIGVzdGFibGlzaGVkIHRvIGRldGVybWluZSB0aGUgbmV3IGZlZGVyYXRpb24mcnNxdW87cyByZWdpb24gY29kZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgbmV3IHJlZ2lvbiBjb2RlIG11c3QgYmUgZm9ybWVkIGJ5IHNlbGVjdGluZyBvbmUgb3IgbW9yZSBvZiB0aGUgZXhpc3RpbmcgcmVnaW9uIGNvZGVzIGFuZCB0aGVuIHJlYXJyYW5naW5nIHRoZWlyIGNoYXJhY3RlcnMuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXcgcmVnaW9uIGNvZGUgbXVzdCBiZSBhIDxzdHJvbmc+cGFsaW5kcm9tZTxcL3N0cm9uZz4gdG8gbWFrZSBpdCBlYXNpZXIgdG8gcmVtZW1iZXIuIEEgcGFsaW5kcm9tZSBpcyBhIHN0cmluZyB0aGF0IHJlYWRzIHRoZSBzYW1lIGJhY2t3YXJkIGFzIGZvcndhcmQuPFwvbGk+XHJcblx0PGxpPkFtb25nIGFsbCB2YWxpZCBvcHRpb25zLCB0aGUgbmV3IHJlZ2lvbiBjb2RlIG11c3QgYmUgdGhlIHNob3J0ZXN0IHBvc3NpYmxlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciB0aGUgc2FrZSBvZiBVRFBDJnJzcXVvO3MgdW5pdHksIGRldGVybWluZSB0aGUgbmV3IGZlZGVyYXRpb24mcnNxdW87cyByZWdpb24gY29kZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgJE4kLCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiByZWdpb25zLiAkKDEgXFxsZSBOIFxcbGUgMTBeNikkPFwvcD5cclxuXHJcbjxwPlRoZSAkaSQtdGggb2YgdGhlIGZvbGxvd2luZyAkTiQgbGluZXMgY29udGFpbnMgYSBub25lbXB0eSBzdHJpbmcgJFNfaSQsIHRoZSByZWdpb24gY29kZSBvZiB0aGUgJGkkLXRoIHJlZ2lvbi48XC9wPlxyXG5cclxuPHA+RWFjaCBzdHJpbmcgY29uc2lzdHMgb25seSBvZiBkaWdpdHMgZnJvbSAkMCQgdG8gJDkkLCBhbmQgaXQgaXMgZ3VhcmFudGVlZCB0aGUgdG90YWwgbGVuZ3RoIG9mIGFsbCBzdHJpbmdzIGRvZXMgbm90IGV4Y2VlZCAkMiBcXHRpbWVzIDEwXjYkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCBwcmludCB0aGUgbGVuZ3RoIG9mIHRoZSBuZXcgcmVnaW9uIGNvZGUuIElmIGl0IGlzIGltcG9zc2libGUgdG8gY3JlYXRlIGEgbmV3IHZhbGlkIHJlZ2lvbiBjb2RlLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcblxyXG48cD5JZiBhIG5ldyB2YWxpZCByZWdpb24gY29kZSBjYW4gYmUgZm9ybWVkLCBwcmludCB0d28gbW9yZSBsaW5lcyBhcyBiZWxvdy48XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lLCBwcmludCBhbiBpbnRlZ2VyICRNJCwgdGhlIG51bWJlciBvZiByZWdpb25zIHVzZWQgdG8gY29uc3RydWN0IHRoZSBuZXcgcmVnaW9uIGNvZGUuPFwvcD5cclxuXHJcbjxwPk9uIHRoZSB0aGlyZCBsaW5lLCBwcmludCAkTSQgaW50ZWdlcnMgaW4gYXNjZW5kaW5nIG9yZGVyLCB0aGUgPHN0cm9uZz5yZWdpb24gbnVtYmVyczxcL3N0cm9uZz4mbmJzcDtvZiB0aGVzZSAkTSQgcmVnaW9ucy48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIG11bHRpcGxlIHBvc3NpYmxlIHNvbHV0aW9ucywgcHJpbnQgYW55IG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==