cho.sh

메시지 라우팅

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

국제표준화기구(ISO)는 X.400이라는 메시지 처리 시스템(MHS, Message Handling System)을 정의했다. MHS의 기능 단위 중 하나인 메시지 전송 에이전트(MTA, Message Transfer Agent) 는 메시지의 라우팅을 담당한다.

라우팅은 메시지의 발신자/수신자 이름(O/R 이름, Originator/Recipient name) 을 이루는 구성 요소를 기준으로 이루어진다. 이 문제에서 O/R 이름은 범위가 넓은 것부터 좁은 것 순서로 다음 네 가지 구성 요소를 가진다.

  1. 국가(Country, C)
  2. 관리 도메인(ADMD, Administrative Management Domain)
  3. 사설 관리 도메인(PRMD, Private Management Domain)
  4. 조직 이름(Organization Name, O)

모든 MTA는 자신만의 라우팅 테이블을 가지고 있으며, 이를 사용해 메시지를 다음 MTA로 전달하거나 로컬로 배달한다.

여러 MTA가 메시지를 처리하는 과정을 시뮬레이션하라. 메시지가 어떤 MTA에 도착(또는 최초 제출)하면, 그 MTA는 메시지의 O/R 이름을 자신의 라우팅 테이블과 대조하여 메시지를 어디로 보낼지 결정한다. 선택된 목적지가 자기 자신이면 메시지를 로컬로 배달한다. 각 메시지가 MTA들을 거쳐 가는 경로를 추적하면 된다.

라우팅 테이블을 사용하는 방법. 라우팅 테이블의 각 항목은 정확히 하나의 목적지 MTA와, O/R 이름의 네 구성 요소에 대응하는 네 개의 필드로 이루어진다. 하나의 MTA가 여러 항목에 나타날 수 있다. MTA는 라우팅 테이블을 위에서부터 아래로 훑으면서, 네 필드가 메시지의 네 O/R 이름 구성 요소와 모두 일치하는 첫 번째 항목을 선택하고, 그 항목이 가리키는 MTA로 메시지를 전달한다. 필드는 별표 * 로 표기되는 와일드카드일 수 있는데, 와일드카드는 대응하는 O/R 이름 구성 요소의 값과 항상 일치한다. 와일드카드가 아닌 필드는 메시지의 구성 요소와 정확히 같을 때만 일치한다.

오류 처리.

  • 순환 라우팅. 메시지가 경로상에서 이미 한 번 처리했던 MTA에 다시 도착하면, 그 MTA는 라우팅 순환(루프)을 감지하여 메시지를 폐기하고 배달 불가 보고서를 생성한다.
  • 라우팅 불가. 메시지의 O/R 이름과 일치하는 라우팅 테이블 항목이 하나도 없으면, 그 MTA는 메시지를 라우팅할 수 없어 메시지를 폐기하고 라우팅 오류 보고서를 생성한다.

입력

입력은 여러 개의 라우팅 시나리오로 이루어지며, 파일의 끝에서 종료된다.

각 시나리오는 정수 $M$ ($1 \le M \le 10$) 하나가 적힌 줄로 시작한다. $M$은 시나리오에 등장하는 MTA의 수이다. 이어서 $M$개의 MTA에 대한 설명이 나온다.

각 MTA 설명은 MTA 이름과 정수 $I$ ($0 \le I \le 9$)가 적힌 줄로 시작하며, $I$는 그 MTA의 라우팅 테이블 항목 수이다. 이어지는 $I$개의 줄은 각각 하나의 항목을 나타내며, 인접한 MTA의 이름과 그 뒤에 네 개의 O/R 이름 필드(국가, ADMD, PRMD, 조직 이름)를 이 순서대로 담는다.

모든 이름(MTA 이름과 O/R 이름 구성 요소)은 공백이 없는 1~10자의 알파벳 문자열이다. 라우팅 항목의 네 O/R 필드는 각각 별표 * 하나로 대체되어 와일드카드를 나타낼 수도 있다. 한 줄의 모든 필드는 공백으로 구분된다.

MTA 설명이 끝나면 정수 $N$ ($0 < N < 32768$) 하나가 적힌 줄이 나오는데, $N$은 시뮬레이션할 메시지의 수이다. 이어지는 $N$개의 줄은 각각 하나의 메시지를 나타내며, 메시지가 제출되는 MTA의 이름(위에서 설명한 MTA 중 하나)과 그 뒤에 메시지의 네 O/R 이름 구성 요소(국가, ADMD, PRMD, 조직 이름)를 담는다.

출력

각 시나리오에 대해 Scenario # X 를 출력한다. 여기서 $X$는 시나리오 번호로, 1부터 시작하여 시나리오마다 1씩 증가한다.

그다음, 제출 순서대로 $N$개의 메시지 각각에 대해 한 줄을 출력한다. 이 줄은 메시지 번호(1부터 시작)와 그 뒤에 곧바로 이어지는 다음 세 가지 중 정확히 하나로 이루어진다.

  • -- delivered to MTA_NAME
  • -- circular routing detected by MTA_NAME
  • -- unable to route at MTA_NAME

여기서 MTA_NAME은 보고서를 생성한 MTA의 이름으로 대체된다. 각 문자열은 앞의 공백, 대시, 간격을 포함하여 위와 정확히 똑같이 출력해야 한다.

연속한 시나리오 사이는 빈 줄 하나로 구분한다. 마지막 시나리오 뒤에는 빈 줄을 출력하지 않는다.