닌자 저택 지도

오래된 문서에 따르면 가나자와시의 닌자 저택은 사실 미로처럼 설계한 요새였다. 방과 방은 숨겨진 문으로 복잡하게 이어져 있어서 침입자는 길을 잃는다. 모든 방에는 문이 두 개 이상 있다.

닌자 저택은 그림 1처럼 그래프로 나타낼 수 있다. 원 하나가 방 하나를 뜻하고, 두 원을 잇는 선 하나가 두 방 사이의 문 하나를 뜻한다.

그림 1	그림 2

지도가 없어서 직접 그리기로 했다. 탐험 기록을 보고 지도를 완성하는 것이 이 문제다.

바깥으로 열린 입구 하나로 들어가 탐험을 시작했다. 걸어간 경로는 그림 2에 화살표가 달린 선으로 그려 두었다. 방을 오가는 규칙은 다음과 같다.

방에 들어가면 가장 오른쪽 문부터 열고 다음 방으로 간다. 문 너머의 방을 이미 방문했다면 들어가지 않고 문을 닫은 다음, 그다음으로 오른쪽에 있는 문을 연다. 한 방의 문을 모두 살펴보면 그 방에 들어올 때 쓴 문으로 되돌아 나간다. 반대편 방에서 이미 열어 본 문은 다시 열지 않는다. 따라서 문 하나는 탐험 전체에서 딱 한 번 열린다.

첫 번째 방에서 떨어진 거리를 세는 계수기를 들고 다닌다. 새 방에 들어가면 계수기가 1 늘고, 방에서 되돌아 나오면 1 준다. 그림 2에서 괄호 안의 수는 그 방에 들어갔을 때의 계수기 값, 즉 첫 번째 방에서 떨어진 거리다. 괄호가 없는 수는 방문한 순서다.

탐험하면서 기록을 남긴다. 기록의 맨 앞에는 첫 번째 방의 문 개수를 적는다. 바깥으로 통하는 입구는 이 개수에 넣지 않는다. 그 뒤로는 문을 열 때마다 다음 규칙에 따라 수를 하나씩 적는다.

1. 문 너머가 처음 보는 방이면 그 방의 문 개수를 적는다. 이 값은 양수다.
2. 문 너머가 이미 방문한 방 $R$이면 $R$의 거리에서 지금 있는 방의 거리를 뺀 값을 적는다. 이 값은 음수다.

그림 2의 예를 보자. 첫 번째 방은 다른 방과 이어진 문이 세 개이므로 먼저 3을 적는다. 이어서 문이 세 개씩인 두 번째, 세 번째, 네 번째 방으로 옮겨 가며 3 3 3을 덧붙인다. 네 번째 방에서 첫 번째 방으로 들어가지 않고 건너뛸 때는 거리 차이인 -3을 덧붙인다. 이렇게 탐험을 마치면 기록은 3 3 3 3 -3 3 2 -5 3 2 -5 -3이 된다.

시내에는 닌자 저택이 수십 채 있다. 저택마다 기록이 하나씩 주어진다. 저택마다 그래프를 하나씩 출력하라.

첫째 줄에 방문한 닌자 저택 기록의 개수 $n$이 주어진다. $n$은 100보다 작다. 이어서 기록이 $n$개 주어진다. 기록 하나는 한 번의 탐험에서 적은 수를 차례로 나열하고 맨 뒤에 0을 붙인 것이다. 기록 하나는 한 줄 이상으로 이루어지고, 각 줄의 길이는 1000자보다 짧다. 수와 수는 공백이나 줄바꿈으로 구분한다. 저택 하나의 방 개수는 100보다 작고, 방 하나의 문 개수는 40보다 작다.

방이 $m$개인 저택마다 $m$줄을 출력한다. 그중 $i$번째 줄의 형식은 다음과 같다.

i r1 r2 ... rki

$r_1$부터 $r_{k_i}$까지는 방 $i$와 이웃한 방의 번호이고, $k_i$는 방 $i$의 문 개수다. 수와 수는 공백 하나로만 구분한다. 방 번호는 방문한 순서대로 1부터 매긴다. $r_1, r_2, \dots, r_{k_i}$는 오름차순으로 출력한다. 방 $i$와 다른 방이 문 두 개 이상으로 이어져 있을 수 있다. 이때는 그 방 번호를 이어진 문의 개수만큼 되풀이해서 출력한다.