우주를 지키는 검색 라우팅
시간 제한5초메모리 제한512 MB
각 질의가 특정 검색 엔진의 이름과 같을 때, 자기 이름과 같은 질의를 받지 않도록 엔진을 바꾸는 최소 횟수를 구한다.
문제
구글 홈페이지에서 "구글"을 검색하면 우주가 붕괴한다는 이야기가 있다. 물론 농담이다. 검색해 봐도 아무 일도 일어나지 않는다.
하지만 어떤 먼 우주에서는 검색 엔진에 그 엔진의 이름과 똑같은 질의를 보내면 우주가 붕괴한다.
사람들은 이 사고를 막으려고 모든 질의를 한곳에 모아 중앙 시스템에 넘긴다. 중앙 시스템은 검색 엔진 하나를 골라 질의를 보내고, 언제든 다른 엔진으로 바꿀 수 있다. 질의는 받은 순서대로 처리해야 하며, 질의와 이름이 같은 엔진에는 절대 그 질의를 보낼 수 없다.
비용을 줄이려면 엔진을 바꾸는 횟수가 가장 적어야 한다. 중앙 시스템을 최적으로 운영할 때 엔진을 몇 번 바꾸어야 하는지 구하라.
입력
첫째 줄에 테스트 케이스의 개수 이 주어진다. 이어서 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄에는 검색 엔진의 개수 가 주어진다. 다음 개의 줄에는 검색 엔진의 이름이 한 줄에 하나씩 주어진다. 이름의 길이는 100자를 넘지 않고, 영문 대문자와 소문자, 공백, 숫자로만 이루어진다. 같은 이름을 가진 엔진은 없다.
그다음 줄에는 들어온 질의의 개수 가 주어진다. 다음 개의 줄에는 질의가 한 줄에 하나씩 주어진다. 각 질의는 그 테스트 케이스에 나온 검색 엔진 이름 중 하나와 정확히 같다.
제한
출력
각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.
Case #X: Y
는 1부터 시작하는 테스트 케이스 번호이고, 는 검색 엔진을 바꾸는 최소 횟수다. 처음에 엔진을 고르는 것은 바꾼 횟수에 넣지 않는다.
힌트
첫 번째 예제에서는 Dont Ask로 시작해서 여덟 번째 질의를 처리한 뒤 NSM으로 바꾸면 한 번만 바꾸어도 된다.
두 번째 예제에서는 B9 하나로 모든 질의를 처리할 수 있어서 한 번도 바꾸지 않는다.
이름에 공백이 들어갈 수 있으므로 입력은 줄 단위로 읽어야 한다.