테세우스와 미노타우로스

고전 교육을 받은 사람이라면 테세우스와 미노타우로스의 전설을 기억할 것이다. 황소 머리를 한 괴물, 비슷비슷하게 구불구불한 통로로 가득한 지하 미로, 사랑에 빠진 아가씨들, 그리고 실타래가 등장하는 믿기 어려운 이야기다. 이 대회의 교육적 취지에 맞추어, 이제 그 진짜 이야기를 밝힌다.

사실 미로는 비교적 곧은 통로로 연결된 여러 개의 동굴로 이루어져 있었고, 그중 일부 통로는 한 방향으로만 지나갈 수 있었다. 미노타우로스를 가두기 위해, 테세우스는 미노타우로스가 빛을 무서워한다는 사실을 알아내고 미궁 안으로 많은 양의 양초를 몰래 들여왔다. 테세우스는 정처 없이 헤매다가 어느 통로를 따라 다가오는 미노타우로스의 소리를 들었다. 그 순간 그는 양초에 불을 붙이고 추격을 시작했다. 미노타우로스는 방금 떠나온 동굴로 되돌아가 다른 통로로 달아났다. 테세우스는 조금씩 거리를 좁히며 뒤쫓았고, 양초에 불을 붙인 뒤 지나온 $k$번째 동굴에 이르렀다. 그곳에서 그는 켜져 있던 양초를 동굴 한가운데에 놓고, 거기서 새 양초에 불을 붙인 뒤 추격을 계속할 만큼의 시간을 벌었다. 추격이 진행되면서 지나가는 $k$번째 동굴마다 양초가 하나씩 남겨졌고(추격이 시작된 동굴을 첫 번째로 센다), 이로써 미노타우로스의 이동은 점점 제한되었다.

미노타우로스는 어떤 동굴에 들어설 때마다 그 동굴의 출구들을 정해진 순서대로 살펴보고, 불이 켜진 동굴로 곧장 이어지지 않는 첫 번째 출구로 달아났다. 테세우스가 불붙은 양초를 들고 바로 뒤를 쫓고 있었기 때문에, 미노타우로스는 방금 들어온 통로로는 결코 동굴을 빠져나가지 않았다. 결국 미노타우로스는 갇히게 되었고, 테세우스는 그를 물리칠 수 있었다.

미노타우로스가 각 동굴의 출구를 알파벳 순서로 살펴보는 다음 미궁을 예로 들어 보자.

테세우스가 동굴 C에 있을 때 A 쪽에서 다가오는 미노타우로스의 소리를 들었고, $k = 3$이라고 하자. 그는 양초에 불을 붙이고 추격에 나서, 미노타우로스를 A, B, D(양초를 남김), G, E, F(양초를 남김), H, E, G(양초를 남김), H, E(마침내 갇힘)의 순서로 뒤쫓는다.

테세우스의 추격을 시뮬레이션하는 프로그램을 작성하라. 미궁 정보는 각 동굴을 대문자로 나타내며, 각 동굴에 대해 그 동굴에서 도달할 수 있는 동굴들을 미노타우로스가 시도할 순서대로 나열한다. 그 뒤에는 처음 마주쳤을 때 미노타우로스와 테세우스가 각각 있던 동굴의 식별자, 그리고 $k$의 값이 이어진다.

입력은 여러 줄로 이루어지며, 각 줄은 아래 형식으로 하나의 시나리오를 기술한다. 어떤 줄도 255자를 넘지 않는다. 입력은 # 한 글자만 있는 줄로 끝난다.

각 시나리오 줄의 형식은 다음과 같다.

maze. M T k

maze는 세미콜론(;)으로 구분된 동굴:이웃들 항목의 목록이며, 마침표(.)로 끝난다. 각 항목은 동굴의 대문자 식별자, 콜론, 그리고 그 동굴에서 도달할 수 있는 동굴들의 식별자를 미노타우로스가 시도할 순서대로 나열한다. 예를 들어 A:BCD는 동굴 A에서 미노타우로스가 먼저 B를, 그다음 C를, 그다음 D를 시도한다는 뜻이다.
M은 처음 마주쳤을 때 미노타우로스가 있던 동굴의 식별자이고, T는 그때 테세우스가 있던 동굴의 식별자이다.
k는 양의 정수로, 추격이 지나가는 $k$번째 동굴마다 양초가 하나씩 남겨진다.

테세우스와 미노타우로스

문제

입력

출력