Reconstruction#8582
The young programmers Peter and Stancho were hired by two cosmic agencies. The agency of Peter designed a new cosmic station, composed of modules, labeled from to . Some couples of different modules are linked by corridors in such way that it is possible to go from each module to each other module by unique path of corridors (see the Figure). The length of each of the corridors is positive integer. There is no more than one corridor that links two modules. The chiefs of Peter would like to keep in secret the project. That is why Peter encoded the topology of the station giving for each two modules the distance between them (i.e. the sum of the lengths of the corridors on the unique path between the modules).
Now Stancho has a difficult task - he promised to his bosses to decrypt the coding of Peter and to reconstruct the topology of the station. Unfortunately, Stancho is not experienced enough. Help him. Write a program that solves the task.
The first line contains the number (3 \leq n \leq 1024) of the modules. Then n - 1 lines follow. On the first of these lines the distances from module to modules 2, 3, \ldots, n are given, separated by single spaces. On the second line are given, separated by single spaces also, the distances from module to modules 3, 4, \ldots, n, and so on. The last line contains only the distance from module n - 1 to module . All distances are positive integers not greater than .
The program has to print lines. The first line has to contain the list of the neighbors of module , i.e. the modules that are linked with corridors to it. The list has to start with the number of neighbors followed by their labels, sorted in increasing order. All numbers have to be separated by single spaces. On the second row of the output, formatted in the same way, the list of the neighbors of module has to be printed, and so on. The output has to finish with the list of the neighbors of module .
Esempio 1