벽 칠하기
시간 제한5초메모리 제한128 MB
n×n 격자에서 특정 색이 이미 두 칸 이상 있는 행이나 열만 그 색으로 다시 칠할 수 있다는 규칙 아래, 전체를 한 색으로 만드는 데 필요한 최소 이동 횟수와 그 횟수로 가능한 모든 색을 구하는 문제입니다.
문제
개의 타일로 이루어진 벽이 있다. 오래전 각 타일은 가지 색 중 하나로 칠해졌다. 이제 페인트가 낡아 벽을 다시 칠해야 하는데, 이번에는 모든 타일을 가지 색 중 단 하나의 색으로 칠해야 한다.
한 번의 이동(move)에서는 타일의 한 가로줄(행) 전체 또는 한 세로줄(열) 전체를 원하는 색으로 다시 칠할 수 있다. 단, 어떤 행이나 열을 색 로 칠하려면 그 줄에 이미 색 인 타일이 (원래 칠해진 것이든 이전 이동으로 칠한 것이든) 적어도 두 개 있어야 한다.
모든 타일은 반드시 (적어도 한 번의 이동으로) 다시 칠해져야 하며, 최종적으로 모든 타일이 같은 색이어야 한다. 이를 위해 필요한 최소 이동 횟수와, 그 최소 횟수로 벽을 칠할 수 있는 색을 구하라.
입력
첫 줄에는 테스트 케이스의 수가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 과 가 주어지며, 은 한 줄의 타일 수, 은 사용할 수 있는 색의 수이다. 이어지는 개의 줄에는 각 줄마다 이상 이하의 정수 개가 주어져, 각 타일의 원래 색을 나타낸다.
출력
각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 벽 전체를 하나의 색으로 다시 칠하는 데 필요한 최소 이동 횟수 를 출력한다. 둘째 줄에는 정확히 번의 이동으로 벽을 칠할 수 있는 모든 색을 증가하는 순서로, 공백 하나로 구분하여 출력한다. 규칙에 따라 어떤 색으로도 벽을 다시 칠하는 것이 불가능하면 하나만 한 줄에 출력한다.