시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 330 86 66 29.596%

문제

원이는 요즘 유행하는 게임을 하고 있다. 이 게임은 is 라는 단어를 이용해 어떤 사물을 다른 사물로 바꿀 수 있다. 규칙은 다음과 같다.

  • 게임 시작 시 몇 개의 명령을 설정해놓는다.
    • 이 때, 모든 명령의 형태는 p is q 의 형태이며, p, q는 사물이다.
  • 두 사물 p, q에 대해 p is q 라는 명령은 사물 p를 사물 q로 바꾼다.
    • 이러한 행위를 명령을 적용한다고 부른다.

어떤 사물 p에 대해 적용할 수 있는 명령이 두 가지 이상이면, 그 중 아무거나 하나 골라서 적용할 수 있다. (아무 명령도 적용하지 않을 수도 있다.) 그리고 어떤 사물 p에 명령을 한 번 이상 적용한 결과로 다시 p가 나오는 경우는 없다.

게임 초기에 설정된 명령들이 주어졌을 때, Baba에 명령을 적용하여 어떤 사물로 만들 수 있는지 구해보자.

입력

첫 줄에 전체 명령의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

이후 N개의 줄에 걸쳐 명령이 주어진다. 각 명령은 p is q의 형태로 주어지며,  p와 q는 첫 글자가 영문 대문자이고, 나머지 글자는 영문 소문자인 길이 10 이내의 문자열이다.

출력

Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다.

예제 입력 1

1
Rabbit is Carrot

예제 출력 1


						

적용할 수 있는 명령이 아예 없으므로, 아무것도 출력하지 않는다.

예제 입력 2

3
Rabbit is Carrot
Baba is Cat
Cat is Rabbit

예제 출력 2

Carrot
Cat
Rabbit

Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물은 Cat, Rabbit, 그리고 Carrot이다.

예제 입력 3

1
Baba is Rabbit

예제 출력 3

Rabbit

예제 입력 4

4
Baba is Rabbit
Rabbit is Cat
Cat is Wall
Wall is Unist

예제 출력 4

Cat
Rabbit
Unist
Wall
W3sicHJvYmxlbV9pZCI6IjE3ODM5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQmFiYSBpcyBSYWJiaXQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM2OTRcdWM5OTggXHVjNzIwXHVkNTg5XHVkNTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIGlzIFx1Yjc3Y1x1YjI5NCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzViNFx1YjVhNCBcdWMwYWNcdWJiM2NcdWM3NDQgXHViMmU0XHViOTc4IFx1YzBhY1x1YmIzY1x1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGRjXHVjZTU5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhYzhjXHVjNzg0IFx1YzJkY1x1Yzc5MSBcdWMyZGMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMTI0XHVjODE1XHVkNTc0XHViMTkzXHViMjk0XHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5cdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViYTg1XHViODM5XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1YjI5NCBwIGlzIHEgXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YmE3MCwgcCwgcVx1YjI5NCBcdWMwYWNcdWJiM2NcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWMwYWNcdWJiM2MgcCwgcVx1YzVkMCBcdWIzMDBcdWQ1NzQgcCBpcyBxIFx1Yjc3Y1x1YjI5NCBcdWJhODVcdWI4MzlcdWM3NDAgXHVjMGFjXHViYjNjIHBcdWI5N2MgXHVjMGFjXHViYjNjIHFcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkNTg5XHVjNzA0XHViOTdjIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWM4MDFcdWM2YTlcdWQ1NWNcdWIyZTRcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWMwYWNcdWJiM2MgcFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjODAxXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYTg1XHViODM5XHVjNzc0IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjNzc0XHVjMGMxXHVjNzc0XHViYTc0LCBcdWFkZjggXHVjOTExIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWQ1NThcdWIwOTggXHVhY2U4XHViNzdjXHVjMTFjIFx1YzgwMVx1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNTQ0XHViYjM0IFx1YmE4NVx1YjgzOVx1YjNjNCBcdWM4MDFcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuKSBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNWI0XHViNWE0IFx1YzBhY1x1YmIzYyBwXHVjNWQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjJlNFx1YzJkYyBwXHVhYzAwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODQgXHVjZDA4XHVhZTMwXHVjNWQwIFx1YzEyNFx1YzgxNVx1YjQxYyBcdWJhODVcdWI4MzlcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgQmFiYVx1YzVkMCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjODAxXHVjNmE5XHVkNTU4XHVjNWVjIFx1YzViNFx1YjVhNCBcdWMwYWNcdWJiM2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4MDRcdWNjYjQgXHViYTg1XHViODM5XHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJhODVcdWI4MzlcdWM3NDAgcCBpcyBxXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsJm5ic3A7IHBcdWM2NDAgcVx1YjI5NCBcdWNjYWIgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzYwMVx1YmIzOCBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjNjAxXHViYjM4IFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yzc3OCBcdWFlMzhcdWM3NzQgMTAgXHVjNzc0XHViMGI0XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5CYWJhXHVjNWQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1YmIzY1x1Yzc0NCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YzgwMVx1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1YzU0NFx1YmIzNFx1YWM4M1x1YjNjNCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWM4MDFcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NzQgXHVjNTQ0XHVjNjA4IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YywgXHVjNTQ0XHViYjM0XHVhYzgzXHViM2M0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPkJhYmFcdWM1ZDAgXHViYTg1XHViODM5XHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzgwMVx1YzZhOVx1ZDU1YyBcdWFjYjBcdWFjZmNcdWI4NWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViYjNjXHVjNzQwIENhdCwgUmFiYml0LCBcdWFkZjhcdWI5YWNcdWFjZTAgQ2Fycm90XHVjNzc0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3ODM5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFiYSBpcyBSYWJiaXQiLCJkZXNjcmlwdGlvbiI6IjxwPldvbiBpcyBwbGF5aW5nIGEgZ2FtZSBjYWxsZWQmbmJzcDs8ZW0+QmFiYSBpcyBSYWJiaXQ8XC9lbT4uIEluIHRoaXMgZ2FtZSwgeW91Jm5ic3A7Y2FuIHVzZSB0aGUgd29yZCZuYnNwOzxlbT5pczxcL2VtPiZuYnNwO3RvIGNoYW5nZSZuYnNwO2FuIG9iamVjdCBpbnRvIGFub3RoZXIuJm5ic3A7VGhlIHJ1bGVzIG9mIHRoaXMgZ2FtZSBhcmUgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5TZXQgc29tZSZuYnNwO2NvbW1hbmRzIGF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIGdhbWUuXHJcblx0PHVsPlxyXG5cdFx0PGxpPkV2ZXJ5IGNvbW1hbmQgaXMgaW4gdGhlIGZvcm0gb2YgcCBpcyBxLCB3aGVyZSBwIGFuZCBxIGFyZSBvYmplY3RzLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5Gb3IgdHdvIG9iamVjdHMgcCBhbmQgcSwgaWYgeW91IHVzZSB0aGUgY29tbWFuZCAmcXVvdDtwIGlzIHEmcXVvdDssIGl0IGNoYW5nZXMgdGhlIG9iamVjdCBwIGludG8gdGhlIG9iamVjdCBxLlxyXG5cdDx1bD5cclxuXHRcdDxsaT5UaGlzIGFjdGlvbiBpcyBjYWxsZWQmbmJzcDs8ZW0+YXBwbHlpbmcgdGhlIGNvbW1hbmQ8XC9lbT4uPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIG1vcmUgdGhhbiBvbmUgYXBwbGljYWJsZSBjb21tYW5kIGZvciBzb21lIG9iamVjdCBwLCB5b3UgY2FuIHNlbGVjdCBhbmQgYXBwbHkgYW55IG9mIGl0LiAoWW91IG1heSBub3QgYXBwbHkgYW55IGNvbW1hbmRzLikmbmJzcDtBbmQgaXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZXJlIGFyZSBubyBvYmplY3QgdGhhdCBjb21pbmcgYmFjayB0byBpdCBzZWxmIGFzIGEgcmVzdWx0IG9mIGFwcGx5aW5nIHNvbWUgY29tbWFuZHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGNvbW1hbmRzJm5ic3A7b2YgdGhlIGdhbWUsIGZpbmQgYWxsIHRoZSBvYmplY3RzIHRoYXQgY2FuIHJlc3VsdCBmcm9tIGFwcGx5aW5nIHNvbWUgY29tbWFuZCB0byBCYWJhLiAoQmFiYSBpcyB0aGUgbmFtZSBvZiBhbiBvYmplY3QuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUsIHRoZSBudW1iZXIgb2YgY29tbWFuZHMgTigxJm5ic3A7JmxlOyBOJm5ic3A7JmxlOyAxMDAsMDAwKSBpcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBvZiBmb2xsb3dpbmcgTiBsaW5lcywgZWFjaCBjb21tYW5kIGlzIGdpdmVuIGluIHRoZSBmb3JtIG9mIHAgaXMgcS4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHAgYW5kIHEgYXJlIEVuZ2xpc2ggbGV0dGVycyB3aXRoIGxlbmd0aCBsZXNzIG9yIGVxdWFsIHRvIDEwLiBUaGV5IGFsc28gc2F0aXNmeTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5maXJzdCBsZXR0ZXJzIG9mIHAgYW5kIHEgYXJlIGluIHVwcGVyIGNhc2UsPFwvbGk+XHJcblx0PGxpPmFuZCB0aGUgcmVzdCBvZiB0aGUmbmJzcDtsZXR0ZXJzIG9mIHAgYW5kIHEgYXJlIGluIGxvd2VyIGNhc2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCZuYnNwO2FsbCB0aGUgb2JqZWN0cyB0aGF0IGNhbiByZXN1bHQgZnJvbSBhcHBseWluZyBzb21lIChtb3JlIG9yIGVxdWFsIHRoYW4gb25lKSZuYnNwO2NvbW1hbmQgdG8gQmFiYSwgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLiZuYnNwO0hvd2V2ZXIsIGlmIHRoZXJlIGFyZSBubyBhcHBsaWNhYmxlIGNvbW1hbmRzLCBvdXRwdXQgbm90aGluZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+U2luY2UmbmJzcDt0aGVyZSBhcmUgbm8gYXBwbGljYWJsZSBjb21tYW5kcywgb3V0cHV0IG5vdGhpbmcuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPkNhdCwgUmFiYml0LCBhbmQgQ2Fycm90IGNhbiByZXN1bHQgZnJvbSBhcHBseWluZyBzb21lIChtb3JlIG9yIGVxdWFsIHRoYW4gb25lKSBjb21tYW5kIHRvIEJhYmEuPFwvcD5cclxuIn1d