시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 452 112 84 27.451%

문제

유토피아의 왕이 사망했다. 왕은 자손을 남기지 않고 사망했기 때문에, 왕위를 계승할 사람을 지목하지 않았다. 왕실 귀족은 왕위를 주장하기 시작했다. 유토피아의 법에는 왕의 계승자가 없는 경우에, 나라를 세운 사람과 혈통이 가까운 사람이 유토피아를 통치한다는 조항이 있다.

나라를 세운 사람과 혈통이 가장 가까운 사람은 그의 자손이 아닌 사람과 피가 덜 섞인 사람이다. 모든 사람은 아버지의 혈통과 어머니의 혈통을 반 씩 받게 된다. 나라를 세운 사람의 자식은 1/2 왕족이며, 그 아들이 왕족이 아닌 사람과 결혼한 경우에는 아들의 자식은 1/4 왕족이 된다.

가장 나라를 세운 사람과 혈통이 가까운 사람을 찾는 프로그램을 작성하시오. 

입력

첫째 줄에 N과 M이 주어진다. (2 ≤ N, M ≤ 50)

둘째 줄에 유토피아를 세운 사람의 이름이 주어진다.

다음 N개 줄에는 가족 정보가 주어진다. 정보는 이름 세 개로 이루어져 있고, 공백으로 구분되어져 있다. 첫 번째 이름은 자식의 이름이고, 뒤의 두 이름은 부모의 이름이다.

다음 M개 줄에는 왕위를 계승받기를 주장하는 사람의 이름이 한 줄에 하나씩 주어진다.

모든 이름은 1~10글자이며, 알파벳 소문자로만 이루어져 있다. 나라를 세운 사람이 왕위를 계승하는 경우나, 누군가의 자식인 경우는 없다. 

출력

첫째 줄에 유토피아를 세운 사람과 가장 혈통이 가까운 사람의 이름을 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

문제에 주어지는 가족 관계는 성별, 나이를 고려하지 않고 만들었기 때문에, 실제로는 말이 안되는 경우가 나올 수도 있다. 하지만, 모든 자식의 부모는 유일하며, 다시 자식이 부모의 부모가 되는 경우도 없다. 또, 한 사람이 여러 명의 자식이 될 수 도 없다.

예제 입력 1

9 2
edwardi
charlesi edwardi diana
philip charlesi mistress
wilhelm mary philip
matthew wilhelm helen
edwardii charlesi laura
alice laura charlesi
helen alice bernard
henrii edwardii roxane
charlesii elizabeth henrii
charlesii
matthew

예제 출력 1

matthew
W3sicHJvYmxlbV9pZCI6IjUwMjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NTVcdWM3MDQgXHVhY2M0XHVjMmI5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWQxYTBcdWQ1M2NcdWM1NDRcdWM3NTggXHVjNjU1XHVjNzc0IFx1YzBhY1x1YjlkZFx1ZDU4OFx1YjJlNC4gXHVjNjU1XHVjNzQwIFx1Yzc5MFx1YzE5MFx1Yzc0NCBcdWIwYThcdWFlMzBcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzBhY1x1YjlkZFx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzY1NVx1YzcwNFx1Yjk3YyBcdWFjYzRcdWMyYjlcdWQ1NjAgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YzljMFx1YmFhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1YzY1NVx1YzJlNCBcdWFkYzBcdWM4NzFcdWM3NDAgXHVjNjU1XHVjNzA0XHViOTdjIFx1YzhmY1x1YzdhNVx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1YzcyMFx1ZDFhMFx1ZDUzY1x1YzU0NFx1Yzc1OCBcdWJjOTVcdWM1ZDBcdWIyOTQgXHVjNjU1XHVjNzU4IFx1YWNjNFx1YzJiOVx1Yzc5MFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwLCBcdWIwOThcdWI3N2NcdWI5N2MgXHVjMTM4XHVjNmI0IFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWQ2MDhcdWQxYjVcdWM3NzQgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3MjBcdWQxYTBcdWQ1M2NcdWM1NDRcdWI5N2MgXHVkMWI1XHVjZTU4XHVkNTVjXHViMmU0XHViMjk0IFx1Yzg3MFx1ZDU2ZFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWMxMzhcdWM2YjQgXHVjMGFjXHViNzhjXHVhY2ZjIFx1ZDYwOFx1ZDFiNVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWFkZjhcdWM3NTggXHVjNzkwXHVjMTkwXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWMwYWNcdWI3OGNcdWFjZmMgXHVkNTNjXHVhYzAwIFx1YjM1YyBcdWMxMWVcdWM3NzggXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YzU0NFx1YmM4NFx1YzljMFx1Yzc1OCBcdWQ2MDhcdWQxYjVcdWFjZmMgXHVjNWI0XHViYTM4XHViMmM4XHVjNzU4IFx1ZDYwOFx1ZDFiNVx1Yzc0NCBcdWJjMTggXHVjNTI5IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWMxMzhcdWM2YjQgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc0MCAxXC8yIFx1YzY1NVx1Yzg3MVx1Yzc3NFx1YmE3MCwgXHVhZGY4IFx1YzU0NFx1YjRlNFx1Yzc3NCBcdWM2NTVcdWM4NzFcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWFjYjBcdWQ2M2NcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YjRlNFx1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3NDAgMVwvNCBcdWM2NTVcdWM4NzFcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViMDk4XHViNzdjXHViOTdjIFx1YzEzOFx1YzZiNCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVkNjA4XHVkMWI1XHVjNzc0IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiwgTSAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzcyMFx1ZDFhMFx1ZDUzY1x1YzU0NFx1Yjk3YyBcdWMxMzhcdWM2YjQgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM4NzEgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODE1XHViY2Y0XHViMjk0IFx1Yzc3NFx1Yjk4NCBcdWMxMzggXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0XHVhY2UwLCBcdWI0YTRcdWM3NTggXHViNDUwIFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWJkODBcdWJhYThcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjU1XHVjNzA0XHViOTdjIFx1YWNjNFx1YzJiOVx1YmMxYlx1YWUzMFx1Yjk3YyBcdWM4ZmNcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3NzRcdWI5ODRcdWM3NDAgMX4xMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIwOThcdWI3N2NcdWI5N2MgXHVjMTM4XHVjNmI0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM2NTVcdWM3MDRcdWI5N2MgXHVhY2M0XHVjMmI5XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjA5OCwgXHViMjA0XHVhZDcwXHVhYzAwXHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzIwXHVkMWEwXHVkNTNjXHVjNTQ0XHViOTdjIFx1YzEzOFx1YzZiNCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVhYzAwXHVjN2E1IFx1ZDYwOFx1ZDFiNVx1Yzc3NCBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWMwMFx1Yzg3MSBcdWFkMDBcdWFjYzRcdWIyOTQgXHVjMTMxXHViY2M0LCBcdWIwOThcdWM3NzRcdWI5N2MgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyZTRcdWM4MWNcdWI4NWNcdWIyOTQgXHViOWQwXHVjNzc0IFx1YzU0OFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViMDk4XHVjNjJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYWE4XHViNGUwIFx1Yzc5MFx1YzJkZFx1Yzc1OCBcdWJkODBcdWJhYThcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTU4XHViYTcwLCBcdWIyZTRcdWMyZGMgXHVjNzkwXHVjMmRkXHVjNzc0IFx1YmQ4MFx1YmFhOFx1Yzc1OCBcdWJkODBcdWJhYThcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHViYTg1XHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTAyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1Y2Nlc3Npb24iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBraW5nIGluIFV0b3BpYSBoYXMgZGllZCB3aXRob3V0IGFuIGhlaXIuIE5vdyBzZXZlcmFsIG5vYmxlcyBpbiB0aGUgY291bnRyeSBjbGFpbSB0aGUgdGhyb25lLiBUaGUgY291bnRyeSBsYXcgc3RhdGVzIHRoYXQgaWYgdGhlIHJ1bGVyIGhhcyBubyBoZWlyLCB0aGUgcGVyc29uIHdobyBpcyBtb3N0IHJlbGF0ZWQgdG8gdGhlIGZvdW5kZXIgb2YgdGhlIGNvdW50cnkgc2hvdWxkIHJ1bGUuPFwvcD5cclxuXHJcbjxwPlRvIGRldGVybWluZSB3aG8gaXMgbW9zdCByZWxhdGVkIHdlIG1lYXN1cmUgdGhlIGFtb3VudCBvZiBibG9vZCBpbiB0aGUgdmVpbnMgb2YgYSBjbGFpbWFudCB0aGF0IGNvbWVzIGZyb20gdGhlIGZvdW5kZXIuIEEgcGVyc29uIGdldHMgaGFsZiB0aGUgYmxvb2QgZnJvbSB0aGUgZmF0aGVyIGFuZCB0aGUgb3RoZXIgaGFsZiBmcm9tIHRoZSBtb3RoZXIuIEEgY2hpbGQgdG8gdGhlIGZvdW5kZXIgd291bGQgaGF2ZSAxXC8yIHJveWFsIGJsb29kLCB0aGF0IGNoaWxkJiMzOTtzIGNoaWxkIHdpdGggYW5vdGhlciBwYXJlbnQgd2hvIGlzIG5vdCBvZiByb3lhbCBsaW5lYWdlIHdvdWxkIGhhdmUgMVwvNCByb3lhbCBibG9vZCwgYW5kIHNvIG9uLiBUaGUgcGVyc29uIHdpdGggbW9zdCBibG9vZCBmcm9tIHRoZSBmb3VuZGVyIGlzIHRoZSBvbmUgbW9zdCByZWxhdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgyICZsZTsgTiAmbGU7IDUwKSBhbmQgTSAoMiAmbGU7IE0gJmxlOyA1MCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgbmFtZSBvZiB0aGUgZm91bmRlciBvZiBVdG9waWEuPFwvcD5cclxuXHJcbjxwPlRoZW4gZm9sbG93cyBOIGxpbmVzIGRlc2NyaWJpbmcgYSBmYW1pbHkgcmVsYXRpb24uIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIHRocmVlIG5hbWVzLCBzZXBhcmF0ZWQgd2l0aCBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IG5hbWUgaXMgYSBjaGlsZCBhbmQgdGhlIHJlbWFpbmluZyB0d28gbmFtZXMgYXJlIHRoZSBwYXJlbnRzIG9mIHRoZSBjaGlsZC48XC9wPlxyXG5cclxuPHA+VGhlbiBmb2xsb3dzIE0gbGluZXMgY29udGFpbmluZyB0aGUgbmFtZXMgb2YgdGhvc2Ugd2hvIGNsYWltcyB0aGUgdGhyb25lLjxcL3A+XHJcblxyXG48cD5BbGwgbmFtZXMgaW4gdGhlIGlucHV0IHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMCBjaGFyYWN0ZXJzIGxvbmcgYW5kIG9ubHkgY29udGFpbiB0aGUgbG93ZXJjYXNlIEVuZ2xpc2ggbGV0dGVycyAmIzM5O2EmIzM5Oy0mIzM5O3omIzM5Oy4gVGhlIGZvdW5kZXIgd2lsbCBub3QgYXBwZWFyIGFtb25nIHRoZSBjbGFpbWFudHMsIG5vciBiZSBkZXNjcmliZWQgYXMgYSBjaGlsZCB0byBzb21lb25lIGVsc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBuYW1lIG9mIHRoZSBjbGFpbWFudCB3aXRoIG1vc3QgYmxvb2QgZnJvbSB0aGUgZm91bmRlci4gVGhlIGlucHV0IHdpbGwgYmUgY29uc3RydWN0ZWQgc28gdGhhdCB0aGUgYW5zd2VyIGlzIHVuaXF1ZS48XC9wPlxyXG5cclxuPHA+VGhlIGZhbWlseSByZWxhdGlvbnMgbWF5IG5vdCBiZSByZWFsaXN0aWMgd2hlbiBjb25zaWRlcmluZyBzZXgsIGFnZSBldGMuIEhvd2V2ZXIsIGV2ZXJ5IGNoaWxkIHdpbGwgaGF2ZSB0d28gdW5pcXVlIHBhcmVudHMgYW5kIG5vIG9uZSB3aWxsIGJlIGEgZGVzY2VuZGVudCBmcm9tIHRoZW1zZWx2ZXMuIE5vIG9uZSB3aWxsIGJlIGxpc3RlZCBhcyBhIGNoaWxkIHR3aWNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=