작업 순서

N(1 <= N <= 1,000)개의 작업으로 이루어진 공정이 있다. 이 공정을 끝내려면 모든 작업을 정확히 한 번씩 수행해야 한다.

각 작업은 한 대의 기계로 수행한다. 어떤 작업을 끝낸 직후에 수행할 수 있는 다음 작업은 미리 정해져 있다. 따라서 여러 작업을 한 번에 연속해서 처리하려면, 그 순서를 작업 시작 전에 기계에 입력해 두어야 한다.

기계가 실제 작업을 처리하는 시간은 매우 짧지만, 작업 순서를 입력하는 데에는 매우 긴 시간이 걸린다. 작업을 하나만 입력하더라도 입력 시간은 길다고 가정한다. 그러므로 모든 작업을 한 번씩 수행하면서, 작업 순서를 입력하는 횟수를 최소화해야 한다.

작업 사이의 관계는 추이적이지 않을 수 있다. 예를 들어 1번 작업 뒤에 2번 작업을 바로 수행할 수 있고, 2번 작업 뒤에 3번 작업을 바로 수행할 수 있어도, 1번 작업 뒤에 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개의 정수는 작업 번호를 수행 순서대로 나타낸다.

모든 작업은 전체 출력에서 정확히 한 번씩 등장해야 한다. 최적해가 여러 개라면 그중 아무 것이나 출력해도 된다.

작업을 1 2 3 순서로 한 번에 입력할 수 있다면 작업 순서를 한 번만 입력하면 된다. 모든 작업을 이미 수행했으므로 공정은 여기서 끝난다.