#P2040. Translations

Translations

描述

Bob Roberts负责在不同语言之间进行文档翻译。为了帮助他完成这项工作,他的上司提供了翻译文件。这些文件成对出现——一个文件包含某种语言的示例短语,另一个文件包含这些短语翻译成另一种语言的结果。然而,某个过于热心的下属为了讨好上级,擅自将所有文件的内容按字母顺序排序,导致短语与其翻译之间的对应关系丢失。幸运的是,由于这些列表非常全面,原始翻译可以从排序后的列表中重新构建。Bob发现,当所有短语都由两个单词组成时,这种情况通常成立。例如,给定以下两个列表:

语言1短语 语言2短语
arlo zym bus seat
flub pleve bus stop
pleve dourm hot seat
pleve zym school bus

Bob可以推断出:

  • arlo 对应 hot
  • zym 对应 seat
  • flub 对应 school
  • pleve 对应 bus
  • dourm 对应 stop

在手动完成多次这样的重建后,Bob决定将这一过程自动化。既然Bob能做到,那么你也能。

输入

输入包含多个输入集。每个输入集以一个正整数n250n \leq 250开头,表示每种语言中两单词短语的数量。随后是2n2n行,每行包含一个两单词短语:前nn行是第一种语言的短语按字母顺序排列的列表,后nn行是这些短语翻译成第二种语言的结果。单词仅包含大小写字母。每个输入集最多涉及2525个不同的单词。对于任何一种语言,没有任何单词作为短语的第一个单词出现超过1010次,同样也没有任何单词作为短语的最后一个单词出现超过1010次。最后一个输入集之后是一行仅包含00,表示输入结束。

输出

对于每个输入集,输出以下形式的行:

word1/word2

其中,word1是第一种语言的单词,word2word1在第二种语言中的翻译,两者用斜杠分隔。输出行应按第一种语言的单词排序,且每个第一种语言的单词只出现一次。输出中不应有空格,不同输入集的输出之间用一个空行分隔。请模仿下面示例输出的格式。每个输入实例保证有唯一正确的翻译。

示例输入

4
arlo zym
flub pleve
pleve dourm
pleve zym
bus seat
bus stop
hot seat
school bus
2
iv otas
otas re
ec t
eg ec
0

示例输出

arlo/hot
dourm/stop
flub/school
pleve/bus
zym/seat

iv/eg
otas/ec
re/t