루미 알고리즘

#1559골드Synonyms

PO 2023 결선코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Sometimes when copying text from Wikipedia into essays, the text can get caught in a plagiarism detection program. To avoid this, one must first rewrite the text in their own words so it doesn't get flagged by the program. There are many ways to do this, one of which is to run the text through a translation program into another language and then back again. If you're unlucky, the text may come back too similar to the original despite this.

You could avoid this problem by ensuring that a word is never translated back to the same word if there is another possibility. Formally, assume we have a dictionary with N pairs of words (a, b), where a is the word in Swedish and b is the word in another language. A certain word x can then be changed to the word y if there exist two pairs (x, z) and (y, z) in the dictionary for some word z.

Given a text, rewrite it by replacing as many words as possible by translating them to the other language and back.

Input

The first line contains the integer N (1 ≤ N ≤ 5000), the number of word pairs in the dictionary.

The following N lines each contain a word pair, with the word in Swedish first, followed by the word in the other language. The same word never appears in both languages, and no word pair appears twice.

This is followed by an integer M (1 ≤ M ≤ 1000), the number of words in the text. The next line contains M words, the text you are to translate. All words appear at least once as a Swedish word in the dictionary.

All words are between 1 and 20 letters long and consist only of letters from a-z. It is not guaranteed that the words are actual real words.

Output

Print M words on a single line, the text where as many words as possible have been replaced with a synonym, using the process described in the task. If there are many possible synonyms for a word, you can choose any of them, as long as it is not the same word.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
156All words in the other language has at least two Swedish translations.
244No additional constraints.

Explanation of sample

There are two translations of “skum”, which are “foam” and “shady”. These can, in turn, be translated back into two different words: “skum” and “fradga”. To avoid translating the word back to “skum”, you must choose “fradga”.

However, for the second word, there is only one translation available, so we have to translate it back to the same word.

예제

예제 1

입력
4
skum foam
skum shady
fradga foam
typ type
2
skum typ
출력
fradga typ

예제 2

입력
3
skum foam
skum shady
fradga foam
2
skum fradga
출력
fradga skum

출처 표기

출처: Programmeringsolympiaden 2023년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.