키보드와 바이러스

콜랴는 자신이 매우 뛰어난 프로그래머라고 생각한다. 그는 힙스터이기도 해서, 키 아래에 고무가 들어 있는 평범한 키보드로는 타이핑하기 싫어한다. 대신 각 키 아래에 진짜 스프링이 들어 있는 유행하는 빈티지 기계식 키보드를 샀다. 키보드가 너무 오래되어 키에 인쇄된 기호는 모두 지워졌지만, 콜랴는 개의치 않는다. 그는 매우 뛰어난 프로그래머이기 때문이다.

콜랴는 이 키보드로 $n$개의 서로 다른 언어를 입력한다. 공교롭게도 각 언어의 글자 수는 키보드의 키 수와 같은 $m$이다. 모든 언어의 모든 기호는 콜랴가 쓰는 인코딩에 포함되어 있어, 각 기호는 1부터 $c$까지의 수로 표현된다. 한 기호는 임의의 개수의 언어에 나타날 수 있지만, 서로 다른 두 언어에는 한쪽에만 있고 다른 쪽에는 없는 기호가 반드시 하나 이상 있다. 1부터 $c$까지의 수 가운데에는 콜랴가 아는 어떤 기호와도 대응하지 않는 수가 있을 수 있다.

콜랴의 친구들은 그가 이 키보드를 어디든 들고 다니며 기계식 키를 요란하게 눌러 주변 사람들을 귀찮게 하는 것에 지쳤다. 그래서 언어를 바꿀 때마다 두 가지 짓궂은 짓을 하는 컴퓨터 바이러스를 만들었다.

• 특정 언어로 바꾸는 대신, 콜랴가 쓰는 $n$개의 언어 중 무작위로 고른 언어로 바꾼다(언어가 그대로일 수도 있다).
• 해당 언어의 키 배열을 임의로 섞는다. 다만 서로 다른 키에는 서로 다른 기호가 대응해야 한다는 조건 하나만 지킨다.

바이러스에 감염된 콜랴는 처음에는 당황했지만, 곧 상황이 그리 나쁘지 않다는 것을 깨달았다. 키를 한 번씩 모두 눌러 보면 각 키가 어떤 기호에 대응하는지 알 수 있고, 그 정보로 현재 켜진 언어를 알아낼 수 있다. 하지만 그는 더 적은 횟수로도 현재 언어를 알아낼 수 있을 것 같다고 생각한다. 콜랴가 친구들에게 자신이 정말 뛰어난 프로그래머임을 보여 줄 수 있도록, 최악의 경우에 현재 언어를 알아내기 위해 필요한 키 입력의 최소 횟수를 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다. $n$은 콜랴가 쓰는 언어의 수이고, $m$은 새 키보드의 키 수이자 모든 언어의 글자 수이다.

이어지는 $n$개의 줄에는 각 언어를 나타내는 $m$개의 기호 번호가 주어진다. 번호는 임의의 순서로 주어진다. 모든 번호는 1부터 $c$까지의 정수이다. $c$는 입력으로 주어지지 않지만 각 테스트 묶음마다 정해져 있다.

$n$, $m$, $c$는 모두 양수임이 보장된다.

최악의 경우에 현재 언어를 알아내기 위해 콜랴가 눌러야 하는 키의 최소 횟수를 정수 하나로 출력한다.

문제에 나온 첫 번째 테스트에서, 콜랴가 운이 없어 $1$과 $3$에 대응하는 키를 누르면 어떤 언어로 입력하고 있는지 알 수 없게 된다.