시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 97 39 35 56.452%

문제

고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.

순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’

현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하지만, 태양이는 나머지 4명을 모두 이기는 방법이 생각이 나지 않는다. 태양이를 도와 꼬리를 무는 선수 나열을 만드는 프로그램을 작성하여라.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 2,000)

둘째 줄부터 N개의 줄에는 N개의 정수가 주어지는데, p+1번째 줄의 q번째 수는 아래 규칙을 만족한다.

  • p번 선수가 q번 선수를 이겼으면 1.
  • p번 선수가 q번 선수에게 졌으면 0.
  • p = q인 경우 0.

단, 태양이는 1번 선수이다.

출력

첫 번째 줄에는 꼬리를 무는 선수 나열의 최대 길이 L을 출력한다.

두 번째 줄에는 꼬리를 무는 선수 나열 S1 S2 … SL을 출력한다. 꼬리를 무는 선수 나열은 다음과 같은 규칙을 만족해야 한다.

  • S1 = 1
  • S1, S2, …, SL는 서로 다르다.
  • 모든 1 ≤ i ≤ L-1에 대해서 Si번 선수는 Si+1번 선수를 이겨야 한다. 다만, SL번 선수가 S1번 선수를 이겨야 할 필요는 없다.

예제 입력 1

5
0 0 0 1 0
1 0 0 1 1
1 1 0 1 0
0 0 0 0 1
1 0 1 0 0

예제 출력 1

5
1 4 5 3 2

예제 입력 2

5
0 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0

예제 출력 2

1
1