Spectrum

Swamp County Consulting이 타깃이라고 부르는 대상 사이의 연결을 기록하는 데이터베이스를 만드는 계약을 따냈다. 여러분의 팀은 저장 구조와 아래 명령어를 구현한다.

타깃은 공백이 들어가지 않은 출력 가능 문자 32자 이하의 문자열이다. 연결은 두 타깃 사이의 양방향 관계다.

한 타깃(이것을 target1이라고 하자)에서 나머지 타깃까지의 홉 수는 다음 규칙으로 정한다.

1. target1과 직접 연결된 타깃은 0홉이다.
2. 0홉 타깃과 직접 연결되어 있으면서 아직 0홉 타깃으로도 target1 자신으로도 세지 않은 타깃은 1홉이다.
3. 같은 방식으로, n홉 타깃과 직접 연결되어 있으면서 0홉부터 n홉까지에 아직 들어가지 않은 타깃은 n+1홉이다.

target1 자신은 홉 수를 받지 않는다.

타깃은 최대 100,000개, 연결은 최대 500,000개다.

명령어

데이터베이스 명령어는 add, associated, connections 세 가지다. 기관은 잊지도 않고 실수하지도 않으므로 타깃과 연결은 절대 지워지지 않는다. 명령어는 줄의 첫 칸에서 시작하고, 명령어와 인자는 공백으로 구분한다. 입력의 한 줄은 80칸을 넘지 않는다. 출력 줄의 앞뒤에는 공백을 넣지 않는다.

add target1

타깃을 연결 없이 데이터베이스에 넣는다. 이미 들어 있으면 아무것도 하지 않는다. 오류가 아니다.

add target1 target2

두 타깃 사이에 양방향 연결을 만든다.

• 둘 중 데이터베이스에 없는 타깃이 있으면 먼저 넣고 연결을 만든다.
• 두 타깃이 이미 연결되어 있으면 아무것도 하지 않는다. 오류가 아니다. 두 타깃 사이의 직접 연결은 최대 하나다.
• target1과 target2가 같은 문자열이면 add target1이라고 적힌 것처럼 처리한다. 오류가 아니다.

connections target1

target1에서 각 홉 수마다 타깃이 몇 개인지 알려 준다.

• 홉 수마다 홉 수, 콜론, 공백 한 칸, 그 홉 수에 해당하는 타깃 개수를 앞자리 0 없이 한 줄에 출력한다. 홉 수 0에서 시작해 타깃 개수가 0이 아닌 마지막 홉 수까지 출력하고 멈춘다.
• target1에 연결이 하나도 없으면 no connections만 적힌 줄을 출력한다.
• target1이 데이터베이스에 없으면 target does not exist만 적힌 줄을 출력한다.

associated target1 target2

두 타깃 사이에 연결이 있는지 알려 준다.

• 경로가 있으면 yes: n을 한 줄에 출력한다. n은 target1을 기준으로 잰 target2의 홉 수다. 콜론 뒤에 공백이 한 칸 있고, n에는 앞자리 0이 없으며, 줄 끝에 공백이 없다.
• 경로가 없으면 no를 한 줄에 출력한다.
• target1이나 target2가 데이터베이스에 없으면 target does not exist만 적힌 줄을 출력한다.
• 타깃은 자기 자신에 대한 홉 수가 없으므로, target1과 target2가 같은 타깃이면 no를 출력한다.

입력에는 여러 개의 케이스가 들어 있다. reset이라고만 적힌 줄은 데이터베이스 명령어가 아니라 앞 케이스의 명령어와 다음 케이스의 명령어를 나누는 구분자다. 이 줄을 읽으면 모든 자료 구조를 초기화한다.

파일 끝까지 읽는다. 입력의 끝을 알리는 표시는 없고, 파일이 reset 줄로 끝나지도 않는다.

케이스마다 Case, 공백 한 칸, 케이스 번호, 콜론으로 이루어진 줄로 시작한다. 케이스 번호는 1부터 센다. 케이스마다 빼기 기호 열 개로 이루어진 줄로 끝낸다.