시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 85 48 39 58.209%

문제

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

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

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

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

입력

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

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

모든 거리는 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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHVjODEwIFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMyAmbGU7IE4gJmxlOyAxMDI0KTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTi0xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YWMwNFx1Yzc1OCBcdWNkNWNcdWIyZThcdWFjNzBcdWI5YWNcdWFjMDAgXHVjNzc4XHVjODExXHVkNTg5XHViODJjIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNSBcdWMxOGRcdWIzYzRcdWI5N2MgXHViZTYwXHViOTc0XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzcwNFwvXHVjNjI0XHViOTc4XHVjYWJkXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOTg5LCAxXHViYzg4IFx1YzkwNFx1YzVkMFx1YjI5NCAyIFwvIDMgXC8gNFx1YzY0MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjLiAyXHViYzg4IFx1YzkwNFx1YzVkMFx1YjI5NCAzIFwvIDQgXC8gNVx1YzY0MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjLi4uIFx1Yzc3NFx1YjdmMCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YWM3MFx1YjlhY1x1YjI5NCAxNTAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjNzc4XHVjODExIFx1YjlhY1x1YzJhNFx1ZDJiOCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVkMmI4XHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1OFx1Yzc5MFx1YmE3NCwgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTc0XHViMmY5IFx1YjE3OFx1YjRkY1x1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM3NzRcdWQ2YzQgXHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjODE1XHVjODEwXHVjNzQwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYwOTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWNvbnN0cnVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvNjA5MVwvMS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTIxcHg7IHdpZHRoOjI2MnB4XCIgXC8+VGhlIHlvdW5nIHByb2dyYW1tZXJzIFBldGVyIGFuZCBTdGFuY2hvIHdlcmUgaGlyZWQgYnkgdHdvIGNvc21pYyBhZ2VuY2llcy4gVGhlIGFnZW5jeSBvZiBQZXRlciBkZXNpZ25lZCBhIG5ldyBjb3NtaWMgc3RhdGlvbiwgY29tcG9zZWQgb2YgTiBtb2R1bGVzLCBsYWJlbGVkIGZyb20gMSB0byBOLiBTb21lIGNvdXBsZXMgb2YgZGlmZmVyZW50IG1vZHVsZXMgYXJlIGxpbmtlZCBieSBjb3JyaWRvcnMgaW4gc3VjaCB3YXkgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBnbyBmcm9tIGVhY2ggbW9kdWxlIHRvIGVhY2ggb3RoZXIgbW9kdWxlIGJ5IHVuaXF1ZSBwYXRoIG9mIGNvcnJpZG9ycyAoc2VlIHRoZSBGaWd1cmUpLiBUaGUgbGVuZ3RoIG9mIGVhY2ggb2YgdGhlIGNvcnJpZG9ycyBpcyBwb3NpdGl2ZSBpbnRlZ2VyLiBUaGVyZSBpcyBubyBtb3JlIHRoZW4gb25lIGNvcnJpZG9yIHRoYXQgbGlua3MgdHdvIG1vZHVsZXMuIFRoZSBjaGllZnMgb2YgUGV0ZXIgd291bGQgbGlrZSB0byBrZWVwIGluIHNlY3JldCB0aGUgcHJvamVjdC4gVGhhdCBpcyB3aHkgUGV0ZXIgZW5jb2RlZCB0aGUgdG9wb2xvZ3kgb2YgdGhlIHN0YXRpb24gZ2l2aW5nIGZvciBlYWNoIHR3byBtb2R1bGVzIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZW0gKGkuZS4gdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiB0aGUgY29ycmlkb3JzIG9uIHRoZSB1bmlxdWUgcGF0aCBiZXR3ZWVuIHRoZSBtb2R1bGVzKS48XC9wPlxyXG5cclxuPHA+Tm93IFN0YW5jaG8gaGFzIGEgZGlmZmljdWx0IHRhc2sgJm5kYXNoOyBoZSBwcm9taXNlZCB0byBoaXMgYm9zc2VzIHRvIGRlY3J5cHQgdGhlIGNvZGluZyBvZiBQZXRlciBhbmQgdG8gcmVjb25zdHJ1Y3QgdGhlIHRvcG9sb2d5IG9mIHRoZSBzdGF0aW9uLiBVbmZvcnR1bmF0ZWx5LCBTdGFuY2hvIGlzIG5vdCBleHBlcmllbmNlZCBlbm91Z2guIEhlbHAgaGltLiBXcml0ZSBhIHByb2dyYW0gcmVjb24gdGhhdCBzb2x2ZXMgdGhlIHRhc2suPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBOIG9mIHRoZSBtb2R1bGVzICgzICZsZTsgTiAmbGU7IDEwMjQpLiBUaGVuIE4gJm5kYXNoOyAxIGxpbmVzIGZvbGxvdy4gT24gdGhlIGZpcnN0IG9mIHRoZXNlIGxpbmVzIHRoZSBkaXN0YW5jZXMgZnJvbSBtb2R1bGUgMSB0byBtb2R1bGVzIDIsIDMsJmhlbGxpcDssIE4gYXJlIGdpdmVuLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gT24gdGhlIHNlY29uZCBsaW5lIHJlIGdpdmVuLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBhbHNvLCB0aGUgZGlzdGFuY2VzIGZyb20gbW9kdWxlIDIgdG8gbW9kdWxlcyAzLCA0LCZoZWxsaXA7LCBOLCBhbmQgc28gb24uIFRoZSBsYXN0IGxpbmUgY29udGFpbnMgb25seSB0aGUgZGlzdGFuY2UgZnJvbSBtb2R1bGUgTiAmbmRhc2g7IDEgdG8gbW9kdWxlIE4uIEFsbCBkaXN0YW5jZXMgYXJlIHBvc2l0aXZlIGludGVnZXJzIG5vdCBncmF0ZXIgdGhhbiAxMDI0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIGhhcyB0byBwcmludCBOIGxpbmVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuIFRoZSBmaXJzdCBsaW5lIGhhcyB0byBjb250YWluIHRoZSBsaXN0IG9mIHRoZSBuZWlnaGJvcnMgb2YgbW9kdWxlIDEsIGkuZS4gdGhlIG1vZHVsZXMgdGhhdCBhcmUgbGlua2VkIHdpdGggY29ycmlkb3JzIHRvIGl0LiBUaGUgbGlzdCBoYXMgdG8gc3RhcnQgd2l0aCB0aGUgbnVtYmVyIEwgb2YgbmVpZ2hib3JzIGZvbGxvd2VkIGJ5IHRoZWlyIGxhYmVscywgc29ydGVkIGluIGluY3JlYXNpbmcgb3JkZXIuIEFsbCBudW1iZXJzIGhhcyB0byBiZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gT24gdGhlIHNlY29uZCByb3cgb2YgdGhlIG91dHB1dCwgZm9ybWF0dGVkIGluJm5ic3A7dGhlIHNhbWUgd2F5LCB0aGUgbGlzdCBvZiB0aGUgbmVpZ2hib3JzIG9mIG1vZHVsZSAyIGhhcyB0byBiZSBwcmludGVkLCBhbmQgc28gb24uIFRoZSBvdXRwdXQgaGFzIHRvIGZpbmlzaCB3aXRoIHRoZSBsaXN0IG9mIHRoZSBuZWlnaGJvcnMgb2YgbW9kdWxlIE4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Tournament in Informatics > Shumen 2010 B1번

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

  • 문제의 오타를 찾은 사람: kalmiaa
  • 문제를 번역한 사람: koosaga