시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB262997337.245%

문제

백남이는 새 학기를 맞이하여, 리그 오브 레게노(League of Legeno)라는 게임을 시작했다. 리그 오브 레게노는 AOS(Aeon of Strife) 종류의 게임으로, 5명의 플레이어가 한 팀이 되어 상대편의 주요 건물을 부수는 것이 게임의 승리 목표이다. 게임 내에서 유저들은 게임에서 승리하기 위해 자신의 캐릭터의 능력치를 올리도록 해야 한다. 맵에 등장하는 몬스터나 상대 팀의 플레이어를 처치하며 경험치와 골드를 보상으로 얻고, 이 경험치를 통해 캐릭터의 레벨을 올림으로써 레벨 증가에 따른 능력치를 얻게 된다. 그러나 한 게임에서 레벨에 대한 일정 상한선이 존재한다. 다른 방법으로는 골드를 사용하여 아이템들을 구매함으로써 자신의 능력치를 높일 수 있다.

아이템 사이에 미리 정해진 구매 순서가 존재한다. 이제 막 게임을 시작한 백남이는 구매 순서 전체가 아니라 두 아이템 사이의 선후관계 일부만 알고 있다. 백남이가 다음 과정을 반복하여 아이템을 구매할 때, 아이템의 전체 구매 순서를 알아내자.

  • 현재 구매할 수 있는 아이템 중 아직 구매하지 않은 아이템을 모두 찾는다.
  • 찾은 아이템을 사전 순으로 모두 구매한다.


 

입력

첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구입하기 위해 앞서 구매해야 하는 것을 의미하며, 아이템 A와 아이템 B는 항상 다르다. 모든 아이템은 선후관계에서 적어도 한 번씩 등장한다. 아이템 이름은 알파벳 소문자로만 이루어져 있고, 공백을 포함하지 않는다. 아이템 이름의 길이는 1 이상 15 이하이다.

출력

먼저 구매해야 하는 아이템부터 순서대로 각 줄에 걸쳐서 출력하라. 단, 모든 아이템을 구매할 수 없다면 -1을 출력한다.

예제 입력 1

4
galeforce everfrost
riftmaker everfrost
goredrinker galeforce
stridebreaker galeforce

예제 출력 1

goredrinker
riftmaker
stridebreaker
galeforce
everfrost

예제 입력 2

2
riftmaker galeforce
galeforce riftmaker

예제 출력 2

-1

예제 입력 3

2
goredrinker galeforce
riftmaker everfrost

예제 출력 3

goredrinker
riftmaker
everfrost
galeforce

출처

University > 충남대학교 > 제5회 생각하는 프로그래밍 대회  E번