Page not loading? Try clicking here.
Placeholder

#8298
Subtask

플로이드-워셜 1s 1024MB

Problems

1번부터 N번까지 번호가 매겨진 N개의 정점으로 이루어진 트리가 있다.

트리의 각 정점에서 정점까지의 최단경로가 저장된 플로이드 워셜 표를 갖고서 해당 트리를 재구성하는 프로그램을 작성하시오.


Input

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

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

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


Output

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

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


Subtask

# Score Condition
#130

N\le 10

#270

추가 제약 조건 없음


Example 

5
5 14 3 7
13 2 6
11 7
4
1 4
1 4
1 5
3 1 2 5
2 3 4


Source

Junior Balkan Olympiad in Informatics 2010
You must sign in to write code.