사다리타기

n명의 사람에게 n개의 선물을 공정하고 무작위로 나누어 주려 한다. 이를 위해 아시아에서 예로부터 널리 쓰이는 기법이 있으며, 보통 무작위 순열을 나타내는 데 사용한다. 중국에서는 귀각(畫鬼腳), 일본에서는 아미다쿠지(あみだくじ), 한국에서는 사다리타기라 부른다. 먼저 용어를 몇 가지 정의하자. 이 사다리는 여러 개의 세로 막대와 인접한 두 세로 막대를 잇는 가로 막대로 이루어진다. 각 세로 막대의 위쪽에서 출발하여 다음 세 단계에 따라 사다리를 따라간다.

1. 세로 막대를 따라갈 때는 처음 만나는 가로 막대의 한쪽 끝에 닿을 때까지 아래로 내려간 뒤, 그 가로 막대를 따라간다.
2. 가로 막대를 따라갈 때는 그 가로 막대의 반대쪽 끝에 닿을 때까지 따라간 뒤, 세로 막대를 따라 아래로 내려간다.
3. 세로 막대의 아래쪽 끝에 닿을 때까지 1단계와 2단계를 반복한다.

그림 D.1(a)는 세로 막대 세 개와 가로 막대 세 개로 이루어진 사다리 L을 보여 준다. 세로 막대에는 왼쪽에서 오른쪽으로 1, …, n의 번호가 붙는다. 이 세 세로 막대를 따라간 경로는 (b), (c), (d)에 나타나 있다. 입력 (1, 2, 3)은 사다리 L에 의해 최종적으로 순열 πL = (3, 2, 1)로 바뀐다. 그림 D.1(e)의 w처럼 바로 인접한 두 가로 막대가 한 점에서 만나는 경우는 허용하지 않는다. 그 점에서 따라갈 방법이 유일하지 않기 때문이다.

그림 D.1: 사다리를 따라가기.

순열 πL을 만드는 사다리 L이 주어진다. 어떤 가로 막대를 포함하는 가로 막대 집합을 제거한 뒤에도 순열 πL이 변하지 않으면, 그 가로 막대는 πL에 대해 불필요하다고 한다. 주어진 πL에 대해 불필요한 가로 막대를 모두 찾아야 한다. 이는 L에서 불필요한 가로 막대를 모두 제거하여 최소 사다리를 만드는 것과 같다. L의 최소 사다리에서 공집합이 아닌 임의의 가로 막대 집합을 제거하면 πL과 다른 순열이 나온다.

입력은 표준 입력에서 읽는다. 첫 줄에 정수 n (3 ≤ n ≤ 50)이 주어지며, n은 세로 막대의 개수이다. 세로 막대는 왼쪽에서 오른쪽 순서로 놓인다. d**i,j는 i번째 세로 막대와 (i + 1)번째 세로 막대 사이에 있는 j번째 가로 막대의 위에서부터의 깊이이며, 1 이상 1,000 이하의 정수이다. 다음 n − 1개의 줄 중 i번째 줄에는 깊이의 나열 d**i,j가 주어지며, 1 ≤ i < n, j ≥ 1이고 d**i,j < d**i,j+1*이다. 이 깊이 나열은 0으로 끝나는데, 0은 깊이가 아니라 나열의 끝을 알리는 표시이다. 그림 D.2를 참고하라.

(a) 가로 막대의 깊이 d**i,j	(b) 예제 입력 1	(c) 예제 입력 2

그림 D.2: 사다리에서 인접한 두 세로 막대 사이에 있는 가로 막대의 깊이.

출력은 표준 출력에 쓴다. πL에 대한 최소 사다리에 남는 가로 막대의 집합을 출력한다. 첫 줄에는 최소 사다리에 남는 가로 막대의 개수 k를 출력한다. 다음 k개의 줄에는 최소 사다리에 남는 가로 막대의 깊이 d**i,j의 두 인덱스 i와 j를 한 줄에 하나씩 출력한다. 최소 사다리는 유일하지 않다.