네트워크 전쟁

때는 2126년, 예언대로 스위프트-터틀 혜성이 지구와 충돌한다. 그 폭발로 고에너지 중성자 구름이 퍼지면서 모든 인류가 사라진다. 뒤이은 전자기 폭풍은 두 가지 특이한 사건을 일으킨다. 전자 네트워크의 여러 부분을 잇던 링크가 다수 끊기고, 몇몇 대학원 인공지능 프로젝트가 마치 수백만 년 전 동물이 그랬던 것처럼 서로 합쳐지고 변이하기 시작한다. 아주 짧은 시간 안에 두 프로그램 Paskill과 Lisper가 출현하여, 네트워크를 돌아다니며 자신이 방문한 노드마다 표시를 남긴다. Paskill은 변형된 Prolog 인터프리터를 실행하고, Lisper는 "Hello World" 프로그램을 실행한다. 그런데 "Hello World"는 무한 루프로 변이하여, 그 노드를 완전히 점유해 버려 어떤 프로그램도(Lisper 자신조차) 그 노드에 다시 들어갈 수 없게 만든다. 한편 Prolog 인터프리터는 자신이 있는 노드로 들어오는 어떤 프로그램이든 즉시 역컴파일하여 파괴한다. 다만 Paskill은 자신이 방문한 노드를 모두 기억하므로 그 노드에 다시 들어가려 하지 않는다. 따라서 Lisper가 Paskill이 이미 방문한 노드에 들어가려 하면 소멸되고, 두 프로그램 모두 Lisper가 이미 방문한 노드에는 들어갈 수 없다. 둘 중 하나라도(또는 둘 다) 움직일 수 없으면 둘 다 멈춘다. 그리고 둘이 같은 노드에 동시에 도착하면 서로를 소멸시킨다. 두 프로그램은 같은 속도로 움직인다.

이 과정을 시뮬레이션하는 프로그램을 작성하라. 네트워크의 모든 노드는 아래 그림처럼 하나의 대문자로 표시된다. 다음 노드로 이동할 때 Paskill은 현재 노드에서 알파벳 순으로 앞쪽을 탐색하고, Lisper는 알파벳 순으로 뒤쪽을 탐색하며, 필요하면 양쪽 모두 끝에서 처음으로 순환한다. 예를 들어 (상대가 없다고 할 때) Paskill이 아래 네트워크의 A에서 출발하면 A, B, C, D, G, H, E, F 순서로 노드를 방문하고, Lisper가 H에서 출발하면 H, G, E, F 순서로 방문한다. 위 사건 중 하나 이상이 일어나면 시뮬레이션을 멈춘다. 사건이 둘 이상 일어나면 Paskill을 먼저 언급한다.

입력은 여러 줄로 이루어진다. 각 줄은 하나의 네트워크와 두 프로그램의 시작 노드를 기술한다. 네트워크는 ';'로 구분된 노드들의 나열로 표현하며 마침표('.')로 끝난다. 각 노드는 식별자, ':', 그리고 그 노드에 연결된 하나 이상의 노드로 기술한다. 모든 링크는 적어도 한 번 언급되며 모든 노드도 마찬가지지만, 모든 노드가 반드시 별도로 '기술'되는 것은 아니다. 마침표 뒤에는 시작 노드의 이름이 나오는데, 먼저 Paskill, 그다음 Lisper이다. 한 줄은 255자를 넘지 않는다. 입력은 '#' 하나만 있는 줄로 끝난다.

출력은 각 네트워크마다 한 줄이다. 각 줄은 종료를 일으킨 사건과 그 사건이 일어난 노드를 명시한다. 종료 사건은 다음 중 하나 또는 둘이다.

• Lisper destroyed in node ?
• {Paskill/Lisper} trapped in node ?
• Both annihilated in node ?