시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 24 3 2 15.385%

문제

유니폼 트리는 레벨이 같은 모든 노드가 같은 개수의 자식을 갖는 트리이다. 각 레벨별로 자식의 수가 모두 같기 때문에, 유니폼 트리는 각 레벨의 자식의 수로 이루어진 정수 리스트로 나타낼 수 있다. 

예를 들어, [2 3 5 0]은 루트의 자식 수가 2이고, 그 자식은 자식을 셋 갖고, 손자는 자식을 다섯 갖고, 증손자는 자식이 없는 트리를 나타낸다.

서브트리는 항상 트리의 루트를 포함해야 한다.

트리의 정보가 주어졌을 때, 그 트리가 갖는 서로 다른 유니폼 서브트리의 개수를 구하는 프로그램을 작성하시오. 아래 그림의 왼쪽은 트리이고, 오른쪽은 그 트리가 갖는 모든 유니폼 서브트리이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 트리 하나를 나타내며, 문자열로 주어진다.

문자열은 여는 괄호와 닫는 괄호로 이루어져 있다. 대응하는 괄호는 노드를 나타내고, 그 사이에 들어있는 노드는 자식을 나타낸다.

노드의 개수는 4,000개를 넘지 않으며, 주어지는 문자열에 괄호를 제외한 다른 문자는 없다.

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

출력

각 테스트 케이스마다, 입력으로 주어진 트리의 서로 다른 유니폼 서브트리를 한 줄에 하나씩 출력한다.

출력은 문제에서 설명한 것과 같이 리스트로 나타내는 방법을 사용하며, 각 숫자 사이에는 공백을 한 칸 출력한다.

리스트는 사전순으로 출력한다.

예제 입력 1

(((()))(()(()())()))
(())
0

예제 출력 1

0
1 0
1 1 0
1 1 1 0
1 1 2 0
1 2 0
1 3 0
2 0
2 1 0
2 1 1 0
0
1 0

힌트

첫 번째 테스트 케이스는 문제의 그림과 같은 트리이다.

W3sicHJvYmxlbV9pZCI6IjcxNTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWIyYzhcdWQzZmMgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWIyYzhcdWQzZmMgXHVkMmI4XHViOWFjXHViMjk0IFx1YjgwOFx1YmNhOFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWFjMTZcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBcdWFjMDEgXHViODA4XHViY2E4XHViY2M0XHViODVjIFx1Yzc5MFx1YzJkZFx1Yzc1OCBcdWMyMThcdWFjMDAgXHViYWE4XHViNDUwIFx1YWMxOVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzcyMFx1YjJjOFx1ZDNmYyBcdWQyYjhcdWI5YWNcdWIyOTQgXHVhYzAxIFx1YjgwOFx1YmNhOFx1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM4MTVcdWMyMTggXHViOWFjXHVjMmE0XHVkMmI4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBbMiAzIDUgMF1cdWM3NDAgXHViOGU4XHVkMmI4XHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWMyMThcdWFjMDAgMlx1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1Yzc5MFx1YzJkZFx1Yzc0MCBcdWM3OTBcdWMyZGRcdWM3NDQgXHVjMTRiIFx1YWMxNlx1YWNlMCwgXHVjMTkwXHVjNzkwXHViMjk0IFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWIyZTRcdWMxMmYgXHVhYzE2XHVhY2UwLCBcdWM5OWRcdWMxOTBcdWM3OTBcdWIyOTQgXHVjNzkwXHVjMmRkXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWIyOTQgXHVkNTZkXHVjMGMxIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4ZThcdWQyYjhcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVkMmI4XHViOWFjXHVhYzAwIFx1YWMxNlx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzcyMFx1YjJjOFx1ZDNmYyBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzU4IFx1YzY3Y1x1Y2FiZFx1Yzc0MCBcdWQyYjhcdWI5YWNcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWFkZjggXHVkMmI4XHViOWFjXHVhYzAwIFx1YWMxNlx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzIwXHViMmM4XHVkM2ZjIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC91dHJlZS5wbmdcIiBzdHlsZT1cImhlaWdodDo0MzVweDsgd2lkdGg6OTIwcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkMmI4XHViOWFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMzAwXHVjNzUxXHVkNTU4XHViMjk0IFx1YWQwNFx1ZDYzOFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHVjNzkwXHVjMmRkXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTc4XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA0LDAwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQyYjhcdWI5YWNcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM3MjBcdWIyYzhcdWQzZmMgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDljXHViODI1XHVjNzQwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVhYzgzXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzAsIFx1YWMwMSBcdWMyMmJcdWM3OTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWQ1NWMgXHVjZTc4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWFjXHVjMmE0XHVkMmI4XHViMjk0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjcxNTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJVbmlmb3JtIFN1YnRyZWVzIiwiZGVzY3JpcHRpb24iOiI8cD5EZWZpbmUgYSBVbmlmb3JtIHRyZWUgYXMgb25lIGluIHdoaWNoIGFsbCBvZiB0aGUgbm9kZXMgYXQgYSBnaXZlbiBsZXZlbCAoaS5lLiBkaXN0YW5jZSBmcm9tIHRoZSByb290KSBoYXZlIHRoZSBzYW1lIGRlZ3JlZSAoaS5lLiBudW1iZXIgb2YgY2hpbGRyZW4pLiBTaW5jZSBhbGwgb2YgdGhlIG5vZGVzIGF0IGEgZ2l2ZW4gbGV2ZWwgaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2YgY2hpbGRyZW4sIGEgdW5pZm9ybSB0cmVlIGNhbiBiZSByZXByZXNlbnRlZCBhcyBzaW1wbHkgYSBsaXN0IG9mIGludGVnZXJzLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgY2hpbGRyZW4gYXQgZWFjaCBsZXZlbC4gRm9yIGV4YW1wbGUsIHRoZSBsaXN0IFsyIDMgNSAwXSByZXByZXNlbnRzIGEgdHJlZSB3aGVyZSB0aGUgcm9vdCBoYXMgMiBjaGlsZHJlbiwgZWFjaCBjaGlsZCBvZiB0aGUgcm9vdCBoYXMgMyBjaGlsZHJlbiwgZWFjaCBncmFuZGNoaWxkIGhhcyA1IGNoaWxkcmVuLCBhbmQgZWFjaCBncmVhdC1ncmFuZGNoaWxkIGhhcyBubyBjaGlsZHJlbiwgYW5kIGlzIHRoZXJlZm9yZSBhIGxlYWYuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciB0aGUgcHVycG9zZXMgb2YgdGhpcyBwcm9ibGVtLCByZWRlZmluZSBTdWJ0cmVlIGFzIGEgY29ubmVjdGVkIHN1YmdyYXBoIG9mIGEgdHJlZSB0aGF0IGluY2x1ZGVzIHRoZSB0cmVlJnJzcXVvO3Mgcm9vdC4gVGhpcyBpcyBhIGJpdCBkaWZmZXJlbnQgdGhhbiB0aGUgdHlwaWNhbCBkZWZpbml0aW9uIG9mIFN1YnRyZWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgZGVzY3JpcHRpb24gb2YgYSB0cmVlLCBmaW5kIGFsbCBvZiB0aGUgdW5pcXVlIFVuaWZvcm0gU3VidHJlZXMgb2YgdGhhdCB0cmVlLiBGb3IgZXhhbXBsZSwgaGVyZSBpcyBhIHRyZWUgYW5kIGFsbCBvZiBpdHMgdW5pcXVlIHVuaWZvcm0gc3VidHJlZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdXRyZWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDM1cHg7IHdpZHRoOjkyMHB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIHNldmVyYWwgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHdpbGwgd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIHRyZWUsIHJlcHJlc2VudGVkIGFzIGEgc2luZ2xlIHN0cmluZyBvbiBvbmUgbGluZS4gVGhlIHN0cmluZyB3aWxsIGJlIGEgc2VxdWVuY2Ugb2YgbWF0Y2hlZCBvcGVuaW5nIGFuZCBjbG9zaW5nIHBhcmVudGhlc2VzLiBFYWNoIG1hdGNoZWQgcGFpciByZXByZXNlbnRzIGEgbm9kZSwgYW5kIHRoZSBzdHJpbmcgYmV0d2VlbiByZXByZXNlbnRzIGl0cyBjaGlsZHJlbi4gVGhlcmUgd2lsbCBub3QgYmUgbW9yZSB0aGFuIDQsMDAwIG5vZGVzIGluIHRoZSB0cmVlLiBUaGVyZSB3aWxsIGJlIG5vIHdoaXRlc3BhY2UsIG9yIGFueSBvdGhlciBjaGFyYWN0ZXJzLCBpbiB0aGUgc3RyaW5nLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGV2ZXJ5IHVuaXF1ZSB1bmlmb3JtIHN1YnRyZWUgb2YgdGhlIGdpdmVuIHRyZWUgYXMgYSBsaXN0IG9mIGludGVnZXJzLCBvbmUgc3VidHJlZSAoYW5kIHRodXMgb25lIGxpc3QpIHBlciBsaW5lLiBQcmludCBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIGludGVnZXJzLCBhbmQgbm8gc3BhY2VzIGFueXdoZXJlIGVsc2UuIERvIG5vdCBwcmludCBhbnkgYmxhbmsgbGluZXMgYmV0d2VlbiBsaXN0cywgb3IgYmV0d2VlbiB0ZXN0IGNhc2VzLiBQcmludCB0aGUgbGlzdHMgZm9yIGEgZ2l2ZW4gdGVzdCBjYXNlIHNvcnRlZCBieSB0aGUgZmlyc3QgZWxlbWVudCwgdGhlbiB0aGUgc2Vjb25kLCB0aGVuIHRoZSB0aGlyZCwgYW5kIHNvIG9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5Ob3RlOiB0aGUgZmlyc3Qgc2FtcGxlIGlucHV0ICZhbXA7IG91dHB1dCBjYXNlIGNvcnJlc3BvbmRzIHRvIHRoZSBwaWN0dXJlZCB0cmVlIGFuZCBzdWJ0cmVlcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==