이름의 날
면접 대비시간 제한1초메모리 제한1024 MB
이름과 한 해의 이름날 목록이 주어질 때, 이름의 글자 하나를 정확히 바꿔 도달할 수 있는 가장 이른 날을 구한다.
문제
친구는 돈을 좋아한다. 이름의 날이 되면 친절한 이모에게서 돈을 받기 때문에, 친구는 이름의 날을 몹시 기다린다.
마침 오늘이 친구의 이름의 날이고, 친구는 다음 이름의 날까지 꼬박 1년을 기다리지 않아도 되는 방법을 생각하고 있다. 당신은 도와달라는 부탁을 받았다.
친구는 다음 이름의 날이 최대한 빨리 오도록 자기 이름에서 글자 하나를 정확히 한 번 바꿀 계획이다. 앞으로 1년간의 이름의 날 목록이 주어지면, 친구의 다음 이름의 날이 얼마나 빨리 올 수 있는지 판단하도록 도와주자. 글자를 추가하거나 지우는 것은 금지되며, 정확히 한 글자를 다른 한 글자로 바꾸는 것만 할 수 있다.
위에 나온 허용된 동작으로 도달할 수 있는 이름을 찾을 수 없다면, 친구는 그냥 1년을 기다려야 한다.
입력
입력은 먼저 친구의 이름인 문자열 하나로 시작한다. 다음 줄에 앞으로 1년간의 날 수인 정수 이 주어진다. 그 뒤에 앞으로 1년간 각 날의 이름의 날을 나타내는 문자열 개가 주어진다.
번째 이름은 항상 친구의 이름이다. 오늘이 친구의 이름의 날이고 따라서 정확히 1년 뒤에도 그렇기 때문이다. 입력에 나오는 이름은 a-z 문자로만 이루어지고 공백을 포함하지 않으며 길이는 최대 10자이다. 앞으로 1년간의 이름은 모두 다르다.
출력
한 줄에 정수 하나를 출력한다. 친구가 이름을 속여 바꾸는 것을 도와줬을 때 다음 이름의 날까지의 최소 일수이다.
힌트
첫 번째 예제에서 친구의 이름은 anna이다. 그녀는 이름의 두 번째 n을 j로 바꿔 anja라는 이름을 만들 수 있고, 예정보다 이틀 빨리 이름의 날을 맞는다. 따라서 답은 3이다. 두 번째 예제에서는 위에 나온 허용된 동작으로 다른 이름을 만들 수 없으므로 jan은 1년, 즉 3일을 기다려야 한다.