시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 86 49 40 58.824%

문제

재현이는 N개의 정점으로 이루어진 트리를 가지고 있었다. 트리는 1~N까지의 번호가 정점에 매겨져 있었으며, 트리를 잇는 N-1개의 간선에는 두 정점을 잇는 거리가 저장되어 있었다. 재현이는 트리를 좋아하는 만큼 트리에게 많은 메모리를 주기 위해서, 모든 간선을 N*N 인접 행렬에 저장했다.

애석하게도, 재현이와 인접 행렬을 모두 싫어하는 수찬이가, 플로이드-와셜 알고리즘을 통해 인접 행렬을 채워버리고 말았다. 재현이에게 남은 건, 두 정점간의 최단거리를 저장해놓은 행렬 뿐이다.

재현이는 흉측하게 변해버린 트리를 본 후, 이제 더이상 트리를 좋아하지 않는다. 재현이는 트리에게 많은 메모리를 주고 싶지 않기에, 트리를 인접 리스트에 저장하려고 한다.

수찬이가 플로이드-와셜 알고리즘을 돌린 인접 행렬이 주어졌을 때, 인접 리스트 형태로 원래 트리를 표현해주자.

입력

첫 번째 줄에 트리의 정점 수 N이 주어진다. (3 ≤ N ≤ 1024)

이후 N-1개의 줄에 트리의 각 노드간의 최단거리가 인접행렬 형태로 주어진다. 입력 속도를 빠르게 하기 위해서 대각선 위/오른쪽만 주어진다. 즉, 1번 줄에는 2,3 .. N 와의 최단거리, 2번 줄에는 3,4 .. N 와의 최단 거리... 이런 식으로 입력이 주어진다.

모든 거리는 15000을 넘지 않는 양의 정수이다.

출력

N개의 줄에 인접 리스트 형태로 트리를 출력하라.

정확히 하자면, i번째 줄에는 해당 노드와 연결되어 있는 정점의 수를 출력하고, 이후 출력한 수만큼 연결된 정점의 번호를 출력하면 된다. 연결된 정점은 오름차순으로 출력되어야 한다.

예제 입력 1

5
5 14 3 7
13 2 6
11 7
4

예제 출력 1

1 4
1 4
1 5
3 1 2 5
2 3 4
W3sicHJvYmxlbV9pZCI6IjYwOTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NTFcdWQwNmMgXHVkNTBjXHViODVjXHVjNzc0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC82MDkxXC8xLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMjFweDsgd2lkdGg6MjYycHhcIiBcLz5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWQyYjhcdWI5YWNcdWIyOTQgMX5OXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YzVjOFx1YzczY1x1YmE3MCwgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc4N1x1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2MgXHVkMmI4XHViOWFjXHVjNWQwXHVhYzhjIFx1YjljZVx1Yzc0MCBcdWJhNTRcdWJhYThcdWI5YWNcdWI5N2MgXHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1Yzc0NCBOKk4gXHVjNzc4XHVjODExIFx1ZDU4OVx1YjgyY1x1YzVkMCBcdWM4MDBcdWM3YTVcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU2MFx1YzExZFx1ZDU1OFx1YWM4Y1x1YjNjNCwgXHVjN2FjXHVkNjA0XHVjNzc0XHVjNjQwIFx1Yzc3OFx1YzgxMSBcdWQ1ODlcdWI4MmNcdWM3NDQgXHViYWE4XHViNDUwIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWMyMThcdWNjMmNcdWM3NzRcdWFjMDAsIFx1ZDUwY1x1Yjg1Y1x1Yzc3NFx1YjRkYy1cdWM2NDBcdWMxNWMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWM3NzhcdWM4MTEgXHVkNTg5XHViODJjXHVjNzQ0IFx1Y2M0NFx1YzZjY1x1YmM4NFx1YjlhY1x1YWNlMCBcdWI5ZDBcdWM1NThcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWIwYThcdWM3NDAgXHVhYzc0LCBcdWI0NTAgXHVjODE1XHVjODEwXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NzRcdWIxOTNcdWM3NDAgXHVkNTg5XHViODJjIFx1YmZkMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1ZDc0OVx1Y2UyMVx1ZDU1OFx1YWM4YyBcdWJjYzBcdWQ1NzRcdWJjODRcdWI5YjAgXHVkMmI4XHViOWFjXHViOTdjIFx1YmNmOCBcdWQ2YzQsIFx1Yzc3NFx1YzgxYyBcdWIzNTRcdWM3NzRcdWMwYzEgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM1ZDBcdWFjOGMgXHViOWNlXHVjNzQwIFx1YmE1NFx1YmFhOFx1YjlhY1x1Yjk3YyBcdWM4ZmNcdWFjZTAgXHVjMmY2XHVjOWMwIFx1YzU0YVx1YWUzMFx1YzVkMCwgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3OFx1YzgxMSBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgXHVjODAwXHVjN2E1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjYzJjXHVjNzc0XHVhYzAwIFx1ZDUwY1x1Yjg1Y1x1Yzc3NFx1YjRkYy1cdWM2NDBcdWMxNWMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YjNjY1x1YjliMCBcdWM3NzhcdWM4MTEgXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3OFx1YzgxMSBcdWI5YWNcdWMyYTRcdWQyYjggXHVkNjE1XHVkMGRjXHViODVjIFx1YzZkMFx1Yjc5OCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTc0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzgxNVx1YzgxMCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDMgJmxlOyBOICZsZTsgMTAyNCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwMSBcdWIxNzhcdWI0ZGNcdWFjMDRcdWM3NTggXHVjZDVjXHViMmU4XHVhYzcwXHViOWFjXHVhYzAwIFx1Yzc3OFx1YzgxMVx1ZDU4OVx1YjgyYyBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjUgXHVjMThkXHViM2M0XHViOTdjIFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjMwMFx1YWMwMVx1YzEyMCBcdWM3MDRcL1x1YzYyNFx1Yjk3OFx1Y2FiZFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzk4OSwgMVx1YmM4OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMiwzIC4uIE4gXHVjNjQwXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhYywgMlx1YmM4OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMyw0IC4uIE4gXHVjNjQwXHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjNzBcdWI5YWMuLi4gXHVjNzc0XHViN2YwIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVhYzcwXHViOWFjXHViMjk0IDE1MDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM3NzhcdWM4MTEgXHViOWFjXHVjMmE0XHVkMmI4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTU4XHVjNzkwXHViYTc0LCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHViMTc4XHViNGRjXHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Yzc3NFx1ZDZjNCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHViOWNjXHVkMDdjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjA5MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlY29uc3RydWN0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC82MDkxXC8xLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMjFweDsgd2lkdGg6MjYycHhcIiBcLz5UaGUgeW91bmcgcHJvZ3JhbW1lcnMgUGV0ZXIgYW5kIFN0YW5jaG8gd2VyZSBoaXJlZCBieSB0d28gY29zbWljIGFnZW5jaWVzLiBUaGUgYWdlbmN5IG9mIFBldGVyIGRlc2lnbmVkIGEgbmV3IGNvc21pYyBzdGF0aW9uLCBjb21wb3NlZCBvZiBOIG1vZHVsZXMsIGxhYmVsZWQgZnJvbSAxIHRvIE4uIFNvbWUgY291cGxlcyBvZiBkaWZmZXJlbnQgbW9kdWxlcyBhcmUgbGlua2VkIGJ5IGNvcnJpZG9ycyBpbiBzdWNoIHdheSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIGdvIGZyb20gZWFjaCBtb2R1bGUgdG8gZWFjaCBvdGhlciBtb2R1bGUgYnkgdW5pcXVlIHBhdGggb2YgY29ycmlkb3JzIChzZWUgdGhlIEZpZ3VyZSkuIFRoZSBsZW5ndGggb2YgZWFjaCBvZiB0aGUgY29ycmlkb3JzIGlzIHBvc2l0aXZlIGludGVnZXIuIFRoZXJlIGlzIG5vIG1vcmUgdGhlbiBvbmUgY29ycmlkb3IgdGhhdCBsaW5rcyB0d28gbW9kdWxlcy4gVGhlIGNoaWVmcyBvZiBQZXRlciB3b3VsZCBsaWtlIHRvIGtlZXAgaW4gc2VjcmV0IHRoZSBwcm9qZWN0LiBUaGF0IGlzIHdoeSBQZXRlciBlbmNvZGVkIHRoZSB0b3BvbG9neSBvZiB0aGUgc3RhdGlvbiBnaXZpbmcgZm9yIGVhY2ggdHdvIG1vZHVsZXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlbSAoaS5lLiB0aGUgc3VtIG9mIHRoZSBsZW5ndGhzIG9mIHRoZSBjb3JyaWRvcnMgb24gdGhlIHVuaXF1ZSBwYXRoIGJldHdlZW4gdGhlIG1vZHVsZXMpLjxcL3A+XHJcblxyXG48cD5Ob3cgU3RhbmNobyBoYXMgYSBkaWZmaWN1bHQgdGFzayAmbmRhc2g7IGhlIHByb21pc2VkIHRvIGhpcyBib3NzZXMgdG8gZGVjcnlwdCB0aGUgY29kaW5nIG9mIFBldGVyIGFuZCB0byByZWNvbnN0cnVjdCB0aGUgdG9wb2xvZ3kgb2YgdGhlIHN0YXRpb24uIFVuZm9ydHVuYXRlbHksIFN0YW5jaG8gaXMgbm90IGV4cGVyaWVuY2VkIGVub3VnaC4gSGVscCBoaW0uIFdyaXRlIGEgcHJvZ3JhbSByZWNvbiB0aGF0IHNvbHZlcyB0aGUgdGFzay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIE4gb2YgdGhlIG1vZHVsZXMgKDMgJmxlOyBOICZsZTsgMTAyNCkuIFRoZW4gTiAmbmRhc2g7IDEgbGluZXMgZm9sbG93LiBPbiB0aGUgZmlyc3Qgb2YgdGhlc2UgbGluZXMgdGhlIGRpc3RhbmNlcyBmcm9tIG1vZHVsZSAxIHRvIG1vZHVsZXMgMiwgMywmaGVsbGlwOywgTiBhcmUgZ2l2ZW4sIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBPbiB0aGUgc2Vjb25kIGxpbmUgcmUgZ2l2ZW4sIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzIGFsc28sIHRoZSBkaXN0YW5jZXMgZnJvbSBtb2R1bGUgMiB0byBtb2R1bGVzIDMsIDQsJmhlbGxpcDssIE4sIGFuZCBzbyBvbi4gVGhlIGxhc3QgbGluZSBjb250YWlucyBvbmx5IHRoZSBkaXN0YW5jZSBmcm9tIG1vZHVsZSBOICZuZGFzaDsgMSB0byBtb2R1bGUgTi4gQWxsIGRpc3RhbmNlcyBhcmUgcG9zaXRpdmUgaW50ZWdlcnMgbm90IGdyZWF0ZXIgdGhhbiAxMDI0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIGhhcyB0byBwcmludCBOIGxpbmVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuIFRoZSBmaXJzdCBsaW5lIGhhcyB0byBjb250YWluIHRoZSBsaXN0IG9mIHRoZSBuZWlnaGJvcnMgb2YgbW9kdWxlIDEsIGkuZS4gdGhlIG1vZHVsZXMgdGhhdCBhcmUgbGlua2VkIHdpdGggY29ycmlkb3JzIHRvIGl0LiBUaGUgbGlzdCBoYXMgdG8gc3RhcnQgd2l0aCB0aGUgbnVtYmVyIEwgb2YgbmVpZ2hib3JzIGZvbGxvd2VkIGJ5IHRoZWlyIGxhYmVscywgc29ydGVkIGluIGluY3JlYXNpbmcgb3JkZXIuIEFsbCBudW1iZXJzIGhhcyB0byBiZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gT24gdGhlIHNlY29uZCByb3cgb2YgdGhlIG91dHB1dCwgZm9ybWF0dGVkIGluJm5ic3A7dGhlIHNhbWUgd2F5LCB0aGUgbGlzdCBvZiB0aGUgbmVpZ2hib3JzIG9mIG1vZHVsZSAyIGhhcyB0byBiZSBwcmludGVkLCBhbmQgc28gb24uIFRoZSBvdXRwdXQgaGFzIHRvIGZpbmlzaCB3aXRoIHRoZSBsaXN0IG9mIHRoZSBuZWlnaGJvcnMgb2YgbW9kdWxlIE4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Tournament in Informatics > Shumen 2010 B1번

Olympiad > Junior Balkan Olympiad in Informatics > JBOI 2010 1번