2059번 - 작업 순서 스페셜 저지

N(1 ≤ N ≤ 1,000)개의 작업으로 이루어진 공정이 있다. 이 공정을 완수하기 위해서는 각각의 작업을 모두 수행하여야 한다.

각각의 작업은 한 대의 기계를 이용하여 수행하게 된다. 기계를 이용하여 어떤 특정 작업을 끝낸 이후에는, 바로 어떤 특정 작업을 수행할 수도 있다. 예를 들어 1번 작업이 종료된 후에 바로 2번 작업을 수행할 수 있는 식이다. 즉, 어떤 작업을 연속적으로 처리하기 위해서는, 그 직전에 수행된 작업이 영향을 받게 된다. 물론, 이를 위해서 제일 첫 번째 작업을 수행하기 전에, 작업들의 순서를 정해서 기계에 입력을 해 두어야 한다.

기계는 작업을 매우 빠른 속도로 처리하기 때문에 실제 작업들이 수행되는 시간은 매우 짧다. 하지만 작업을 시작하기 전에, 기계에 작업 순서를 입력해야 하는데, 이 과정이 복잡하기 때문에 매우 오랜 시간이 걸리게 된다. 단 한 개의 작업만을 처리하는 경우에도, 이러한 작업을 입력하는데 걸리는 시간 역시 매우 길다고 가정하자. 따라서 작업 순서를 입력하는 회수를 최소로 하려 한다. 단, 한 번 수행된 작업을 다시 수행하는 경우가 있어서는 안 되며, 모든 작업을 모두 한 번씩만 수행해야 한다.

작업 순서는 꼭 추이적이진 않을 수도 있다. 예를 들어서 1번 작업이 끝난 이후에 바로 2번 작업을 수행할 수 있고, 2번 작업이 끝난 이후에 3번 작업이 처리될 수도 있다고 하자. 이 경우에 1번 작업이 끝난 이후에 3번 작업을 바로 수행할 수 있는 것은 아닐 수도 있다. 또한 1번 작업이 끝난 이후에 2, 3번 작업을 수행할 수 있다고 하더라도, 1 2 3 순서대로 작업을 수행할 수 있는 것은 아니다. 즉, 2번 작업이 끝난 이후에 3번 작업을 수행할 수 있어야 1 2 3 순서대로 작업을 수행할 수 있다. 또한 영향을 받는 것은 직전 단계에서 수행된 작업이므로, 1번 작업이 끝난 이후에 3번 작업을 수행할 수 있는 것이 아니더라도, 1 2 3 순서대로 작업을 수행할 수도 있다.

단, 각각의 작업 사이에는 어느 정도의 순서 관계가 존재하기 때문에, 서로 다른 두 작업 A, B에 대해서, A가 끝난 이후에 B를 수행할 수 있거나, B가 끝난 이후에 A를 수행할 수 있다(두 경우 모두 성립할 수도 있다).

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 N개의 정수(0 또는 1)가 주어진다. i번째 줄의 j번째 정수가 1일 경우, i번째 작업이 완료된 후 j번 작업을 수행할 수 있음을 의미한다.

첫째 줄에 작업 순서의 입력 회수의 최솟값 X를 출력한다. 다음 X개의 줄에는 각각의 작업 순서를 출력한다. 첫 번째 정수 Y는 작업의 개수이고, 다음 Y개의 정수는 작업 순서를 나타낸다.

작업 순서를 한 번 입력하고, 한 번 입력할 때 3개의 작업 1 2 3을 입력하게 된다. 그리고 남아있는 작업이 없으므로 여기서 종료.