여행자

바이토시아는 예전에 아름답고 교통이 잘 연결된 나라였다. 모든 도시에서 다른 모든 도시로 직접 갈 수 있는 양방향 도로가 있었다. 그 뒤 비토시아가 선전 포고를 하고 비토키 분극 자석(BMP)을 가동했다. 그 영향으로 모든 도로가 일방통행 도로로 바뀌었다. 전쟁은 끝났지만, 자석의 영향으로 바이토시아의 교통은 여전히 혼란스럽다.

유명한 여행자 롱인트 씨는 전쟁 전에 바이토시아의 모든 도시를 도는 여행을 계획했다. 지금은 그런 여행이 불가능할 수도 있어서, 가능한 만큼 많은 도시를 방문하는 것으로 만족해야 할지도 모른다. 롱인트 씨가 여행을 시작할 수 있는 도시마다, 같은 도시를 두 번 지나지 않으면서 방문할 수 있는 서로 다른 도시를 가장 많이 방문하는 경로를 구하라. 여행은 바이토시아의 어느 도시에서든 끝낼 수 있다.

첫째 줄에 도시의 수 $n$ ($2 \le n \le 2000$)이 주어진다. 도시는 1번부터 $n$번까지 번호가 매겨져 있다. 이어서 $n-1$개의 줄이 현재 도로 상태를 나타낸다. $i$번째 줄은 $i+1$번 도시와 그보다 번호가 작은 모든 도시 사이의 도로를 설명한다. 이 줄에는 $i$개의 수가 있으며 각 수는 0 또는 1이다. $j$번째 수가 1이면 $j$번 도시와 $i+1$번 도시 사이의 도로는 $j$에서 $i+1$로 향한다. 0이면 $i+1$에서 $j$로 향한다.

표준 출력에 $n$개의 줄을 출력한다. $i$번째 줄에는 도시 $i$에서 출발하여 같은 도시를 한 번씩만 지나면서 가장 많은 서로 다른 도시를 방문하는 여행 경로를 적는다. 각 줄은 경로에 포함된 도시의 수 $d$ ($d \ge 1$)로 시작하고, 이어서 방문 순서대로 도시 번호 $d$개를 적는다. 수 사이는 한 칸씩 띄운다. 같은 도시에서 길이가 같은 경로가 여러 개 있으면 그중 아무거나 출력해도 된다.