O Jogo

전 세계 사람들은 자신도 모르는 사이에 모두 O Jogo를 하고 있다. 게다가 이 게임을 모르는 사람들이 오히려 이기고 있다! O Jogo는 규칙이 두 개뿐인 아주 단순한 게임이다.

• 누군가 게임을 떠올리면 그 사람은 진다.
• 진 사람은 주변 모든 사람에게 자신이 졌다고 알려야 한다.

방금 당신이 O Jogo에서 졌다. 걱정하지 마라. 게임을 잊는 순간 다시 게임을 하게 된다.

이 게임에는 승자가 없다. 규칙이 패배 조건만 정하기 때문이다. 하지만 당신은 세계에서 가장 큰 마이크로 블로깅 네트워크의 직원이고, 이 게임에 승자가 없다는 사실이 못마땅하다. 그래서 네트워크 사용자 중 게임을 가장 적게 떠올린 사람에게 상을 주기로 한다.

이를 위해 네트워크에서 일어난 모든 사건의 기록을 분석해야 한다. 네트워크는 발행/구독(publish/subscribe) 구조로 동작하며, 다음 세 가지 명령이 있다.

• SUBSCRIBE A, B: 사용자 A가 B를 팔로우한다. A는 B가 보내는 메시지를 받는다.
• UNSUBSCRIBE A, B: 사용자 A가 B의 팔로우를 취소한다.
• PUBLISH A: 사용자 A가 자신을 팔로우하는 모든 사용자에게 메시지를 발행한다.

PUBLISH 메시지는 이미 걸러진 것이다. 기록에는 O Jogo를 알리는 메시지만 남는다. 이런 메시지를 받은 사람은 모두 게임을 떠올린다. 모든 사람이 규칙을 지키는 것은 아니다. 게임을 알리는 메시지를 받고도 친구들에게 알리지 않는 경우가 흔하다. 다만 메시지를 발행한 사람과 받은 사람은 둘 다 게임을 떠올린다.

기록은 한 줄에 명령 하나씩 적힌 평문이다. 각 줄은 명령이 실행된 날을 나타내는 정수로 시작한다. 명령이 없는 날도 있다. 기록은 시간 순서로 주어지며, 같은 날의 명령은 적힌 순서대로 처리된다.

예를 들어 다음 기록을 보자.

123 SUBSCRIBE alice, bob
124 PUBLISH bob
124 PUBLISH alice
126 PUBLISH alice

123일에 alice가 bob을 팔로우하지만 bob은 alice를 팔로우하지 않는다. 다음 날 bob이 게임을 떠올리고 메시지로 alice에게 알린다. 같은 날 alice도 게임을 알리는 메시지를 발행해 팔로워들에게 알린다. 126일에는 alice만 게임을 떠올린다. 따라서 alice는 이틀, bob은 하루 게임을 떠올린 것이다.

사용자 이름은 소문자로만 이루어진 최대 15자의 문자열이다. 게임을 가장 적게 떠올린 사용자를 찾아라. 다시 말해 연속일 필요 없이, 게임을 떠올리지 않고 보낸 날이 가장 많은 사용자를 찾는 것이다.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 기록 항목 수 $n$ ($1 \le n \le 10000$)으로 시작하고, 이어서 위에서 설명한 명령이 한 줄에 하나씩 $n$줄 주어진다. 서로 다른 사용자는 최대 10000명이다. 입력은 $n = 0$인 테스트 케이스로 끝나며, 이 케이스는 처리하지 않는다.

테스트 케이스마다 게임을 가장 적게 떠올린 사용자를 한 줄에 출력한다. 동점이면 해당하는 모든 사용자를 사전순으로 나열하고, 공백 하나로 구분하여 출력한다.