시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32 14 13 52.000%

문제

싸이컴 회원 $M$명은 올해 모두 같은 과목을 수강하며, 이들이 수강하는 과목의 수는 $N$개입니다. 같은 과목이더라도 여러 개의 분반이 있어 같은 분반인 사람들만 함께 강의를 듣게 됩니다. 그런데 놀랍게도 $M$명의 회원들은 모두 서로 다른 분반을 수강해, 적어도 한 개의 수업을 함께 수업을 듣는 사람이 한 쌍도 없었습니다.

싸이컴 회원들은 외로움에서 벗어나기 위해 $K$명의 상상 속 친구를 만들기로 했습니다. 각 친구는 모두 싸이컴 회원들과 같은 종류의 과목을 수강하게 될 것이며, 분반은 자유롭게 정할 수 있습니다. 우리의 목표는 각 사람별로 모든 과목에서 상상 속 친구와 같이 수업을 듣게 하는 것입니다.

$K$는 자유롭게 정할 수 있지만, 상상의 친구가 실제 인간의 수보다 많아서는 안 되기 때문에 $K \le M$을 만족해야 합니다. 또한, 각 싸이컴 회원에 대해 과목 분반 번호가 모두 정확히 겹치는 상상 속 친구가 존재해서는 안 됩니다.

입력

첫 줄에는 과목의 수 $N$과 회원의 수 $M$이 주어집니다.

둘째 줄부터 $M+1$번째 줄까지, $i+1$번 줄에는 정수 $A_{i, 1}, A_{i,2}, \cdots, A_{i, N}$이 주어집니다. $A_{i, j}$는 $i$번 회원이 듣는 $j$번 과목의 분반 번호를 나타냅니다.

출력

첫 줄에는 상상 속 친구의 수 $K$를 출력합니다.

둘째 줄부터 $K+1$번 줄까지, $i+1$번 줄에 정수 $B_{i,1}, B_{i,2}, \cdots, B_{i,N}$을 출력합니다. $B_{i,j}$는 상상 속 $i$번 친구가 듣는 $j$번 과목의 분반 번호를 나타냅니다.

제한

  • $2 \le N \le 1000$
  • $2 \le M \le 1000$
  • 모든 $1 \le i \le N$, $1 \le x < y \le M$에 대해, $A_{x,i} \neq A_{y,i}$입니다. (다시 말해, 싸이컴 회원들은 모든 과목에서 분반이 하나도 겹치지 않습니다.)
  • $1 \le A_{i,j} \le M$
  • $0 \le K \le M$
  • $1 \le B_{i,j} \le M$
  • 모든 $1 \le i \le M$, $1 \le j \le K$에 대해, $A_{i, x} \neq B_{j, x}$이고 $1 \le x \le N$인 $x$가 적어도 하나 존재해야 합니다. (다시 말해, 각 싸이컴 회원에 대해 과목 분반 번호가 모두 정확히 겹치는 상상 속 친구가 존재해서는 안 됩니다.)
  • 모든 $1 \le i \le M$, $1 \le j \le N$에 대해, $A_{i, j} = B_{x, j}$이고 $1 \le x \le K$인 $x$가 적어도 하나 존재해야 합니다. (다시 말해, 각 싸이컴 회원은 모든 과목에서 적어도 한 명의 상상 속의 친구와 같이 수업을 들을 수 있어야 합니다.)

서브태스크

번호 배점 제한
1 20

$A_{i, j} = i$

2 10

$N=M=2$

3 15

$M=2$

4 25

$N=2$

5 80

추가 제한 조건이 없습니다.

예제 입력 1

3 3
1 1 1
2 2 2
3 3 3

예제 출력 1

3
1 2 3
2 3 1
3 1 2

채점 및 기타 정보

  • 예제는 채점하지 않는다.