겨울 축제

동지(冬至)는 오래전부터 북유럽에서 중요한 축제였다. 실제로 기독교가 이를 받아들여 크리스마스로 새롭게 자리매김하기 수천 년 전부터 기념되어 왔다. 뉴질랜드에 처음 정착한 사람들은 열대 지역 출신이어서 동지나 하지가 큰 문제가 되지 않았고, 크리스마스가 중요해진 것은 훨씬 뒤에 온 정착민들이 도착한 뒤였다. 그런데 여러 외래 문화가 그렇듯 옮겨 오는 과정에서 무언가가 어긋났는데, 이 경우에는 바로 ‘시기’였다. 한여름은 휴가와 해변 파티의 계절이라 아무도 다가올 겨울을 떠올리고 싶어 하지 않았고, 특히 나라의 최남단에서는 더욱 그랬다.

그래서 스튜어트 섬 오반의 주민들은 올해 한겨울 파티를 열기로 했다. (그들은 파티를 좋아하고, 어떤 핑계든 없는 것보다는 낫다고 여긴다.) 관습에 따라 모두가 작은 선물을 하나씩 가져오기로 했다. 선물은 사실상 무작위로 나누어졌지만, 누군가 각 선물의 준 사람과 받은 사람을 기록해 두는 좋은 생각을 했다. 이 공동체에서는 빠지는 사람이 없어서 모두가 선물을 하나씩 가져왔고 모두가 하나씩 받았다. 따라서 선물을 주고받는 완전한 순환(A가 B에게 주고, B가 C에게 주고, …, 누군가가 다시 A에게 준다)이 적어도 하나는 존재한다. 다만 파티가 끝난 직후에 그 순환들을 직접 알아내는 일은 주민들에게 조금 벅찼고, 바로 여기서 당신이 나설 차례다.

선물 내역을 읽어 들여, 선물을 주고받는 모든 순환을 찾아내는 프로그램을 작성하라. 모든 사람은 정확히 한 개의 선물을 주고 정확히 한 개의 선물을 받는다고 가정해도 좋다.

입력은 여러 개의 파티로 이루어지며, 각 파티에는 두 개 이상의 선물 내역이 담겨 있다. 각 선물은 한 줄에 하나의 공백으로 구분된 두 이름으로 표현되며, 앞의 사람이 뒤의 사람에게 선물을 주었음을 뜻한다. 각 이름은 최대 20개의 문자로 이루어진다. 한 파티의 인원은 200명을 넘지 않는다. 한 파티의 선물 목록은 오직 # 한 글자만 있는 줄로 끝난다. 전체 파티들의 나열 또한 그러한 줄로 끝난다.

각 파티마다 제목 줄 하나와 그 뒤로 필요한 만큼의 순환 줄을 출력한다. 제목 줄은 Party number 라는 단어들 뒤에 공백 하나와 파티 번호(1부터 시작하는 일련번호)를 붙인 것이다. 순환 줄은 여러 이름을 to 라는 단어로 이어(양쪽에 공백을 하나씩 둔다) 나열하고 마침표(.)로 끝맺은 것이다. 한 순환에서 첫 이름과 마지막 이름은 반드시 같아야 한다. 순환들은 각 순환의 첫 이름이 입력에서 처음 등장하는 순서와 같은 순서로 나열해야 한다. 서로 다른 파티는 빈 줄 하나로 구분한다.