Среди участников соревнований по программированию на сайте codeforces.com распространена традиция: когда участник влюбляется в другого участника, он меняет свой ник (имя, которое видят другие участники) на «I_love_<ник участника, в которого он влюбился>». К сожалению, администрация сайта по техническим причинам утеряла текущие ники участников, которые меняли ники в последнее время, но осталась информация о том, кто из них в кого влюблялся. Теперь администрации нужно написать программу, которая помогала бы определять текущий ник заданного участника. Нужно отметить, что из-за небольшой ошибки в структуре базы данных разные участники на этом сайте могут иметь одинаковые ники.
В первой строке содержится единственное целое число n (2 ≤ n ≤ 200000) — количество участников.
Далее в n строках записаны изначальные ники участников. Каждый из них представляет собой непустую строку длиной не более 24 символов, состоящую только из больших и малых символов латинского алфавита, а также из знаков подчёркивания. Некоторые ники могут совпадать.
В следующей строке содержится единственное целое число m (1 ≤ m ≤ 200000) — количество сообщений о том, что один из участников влюбился в другого участника.
Далее в m строках записаны пары целых чисел aj и bj через пробел (1 ≤ aj, bj ≤ n, aj ≠ bj) — сообщение о том, что aj-й участник влюбился в bj-го участника и поменял ник в соответствии с этим. Участники нумеруются с единицы в том порядке, в котором указаны их изначальные ники. Переименования происходят в том порядке, в котором они указаны.
В единственной строке выведите конечный ник первого участника после всех переименований.
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
6
1 2
3 4
2 1
4 3
1 4
3 2
I_love_I_love_I_love_Tanya_Romanova
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
3
2 1
1 2
1 5
I_love_MikeMirzayanov
2
MikhailRubinchik
evol_I
1
1 2
I_love_evol_I