시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB151250538936.629%

문제

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

나라를 세운 사람과 혈통이 가장 가까운 사람은 그의 자손이 아닌 사람과 피가 덜 섞인 사람이다. 모든 사람은 아버지의 혈통과 어머니의 혈통을 반 씩 받게 된다. 나라를 세운 사람의 자식은 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

예제 입력 2

4 5
andrew
betsy andrew flora
carol andrew betsy
dora andrew carol
elena andrew dora
carol
dora
elena
flora
gloria

예제 출력 2

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