Перенаправить
Веб-поиск работает с электронными документами, доступными по определённым адресам (ссылкам) в сети. Однако адрес документа не всегда уникален, и один и тот же документ может быть доступен по нескольким ссылкам. Рассмотрим особый случай — перенаправление ссылок.
Когда клиент запрашивает страницу по адресу A, сервер может ответить специальным кодом, указывающим на новый адрес B, и клиент переходит по этому адресу. Этот процесс называется перенаправлением. Страница B также может перенаправить клиента на новую страницу C и так далее. Таким образом, один и тот же документ может быть доступен по адресам A, B и C.
Данные о перенаправлениях могут поступать из различных источников, например, от веб-краулера, который берет ссылку A во время обхода и проходит через всю цепочку перенаправлений. Другим источником может быть Twitter API: твиты содержат сокращённые ссылки (tinylinks), а ссылки на оригинальные документы можно получить из расширенных данных в твитах. Если у вас есть несколько источников, могут возникнуть конфликты: например, сначала мы получили данные из Twitter (A->B), затем краулер берет ссылку A, ведущую в D. В качестве альтернативы, сервис мог быть перегружен, и сначала краулер получил ошибку при попытке получить документ A, хотя позже сервис стал доступен, и краулер достиг целевого документа при второй попытке. Также ссылка может стать недействительной, если документ устарел.
Если мы хотим вычислить статистику для документа, например, количество ссылок на него, нам нужно привести все ссылки к некоторому "общему знаменателю". Наиболее практичным "знаменателем" является конечная ссылка в цепочке перенаправлений. U считается конечной ссылкой, если нет перенаправления U->V, ведущего к V. Конечная ссылка также называется истинным адресом документа.
Вам дана информация о N перенаправлениях, каждое из которых представлено парой (u_i, v_i) (1 ≤ i ≤ N), где u_i — оригинальная ссылка, а v_i — ссылка, на которую ведет перенаправление. Перенаправление может быть в форме (u_i, NULL), что означает, что ссылка u_i недействительна. Ссылки даны в порядке поступления, то есть перенаправление, появляющееся позже в списке, содержит более актуальную информацию.
Напишите программу, которая обрабатывает информацию о перенаправлениях и определяет истинный адрес документа для каждой из M ссылок.
При решении задачи могут возникнуть следующие конфликты:
если цепочка перенаправлений для какой-либо ссылки U зациклена, истинный адрес этой ссылки — NULL;
если для какой-либо ссылки U существует несколько вариантов перенаправления, правильным считается последнее перенаправление;
если для какой-либо ссылки U нет информации о перенаправлениях, истинным адресом этой ссылки считается U.
Входные данные
Первая строка входного файла содержит целое число N. Каждая из следующих N строк содержит две ссылки u_i и v_i, разделённые пробелами.
Строка номер N+2 содержит целое число M. Следующие M строк содержат ссылки q_i, для которых необходимо найти истинные адреса.
1 ≤ N, M ≤ 100000
0 < |v_i|, |u_i|, |q_i| ≤ 10. (Длина каждой v_i, u_i, q_i не превышает 10 символов.)
Ссылки могут содержать заглавные и строчные буквы, цифры и следующие 15 символов: "?!#;().%:+-_ /".
Выходные данные
Выходной файл должен содержать M строк, каждая из которых является истинным адресом ссылки q_i.