我们敬爱的侦探夏洛克目前正在努力抓捕一名每天杀人的连环杀手。利用他的推理能力,他了解到凶手有一个选择下一个受害者的策略。
凶手在第一天从两名潜在受害者开始,选择这两名受害者中的一个,杀死选定的受害者并用一个新人取代他。他每天都重复这个过程。这样,他每天就有两个潜在的受害者可供选择。 Sherlock认识最初的两个潜在受害者。此外,他还知道某一天发生的谋杀案以及取代该受害者的新人。
你需要帮助他每天找到所有成对的潜在受害者,以便 Sherlock 能够观察到一些模式。
输入
第一行输入包含两个名字(每个名字的长度不超过10),这两个名字的首字母可能是受害者。下一行包含整数 n (1 ≤ n ≤ 1000),即天数。
接下来n行包含两个名字(每个名字的长度不超过10),第一个是当天被谋杀的人,第二个是取代该人的人。
输入格式一致,即被谋杀的人保证来自当时的两个潜在受害者。此外,所有名称都保证是不同的,并且由小写英文字母组成。
输出
输出n + 1行,第i行应包含凶手选择进行第i次谋杀的两个人。第 (n + 1) 行应包含从中选择下一个受害者的两个人。在每一行中,两个名字可以按任意顺序打印。
示例
输入 #1
ross rachel 4 ross joey rachel phoebe phoebe monica monica chandler
输出 #1
ross rachel joey rachel joey phoebe joey monica joey chandler
输入 #2
icm codeforces 1 codeforces technex
输出 #2
icm codeforces icm technex
注意
在第一个示例中,凶手从罗斯和雷切尔开始。
- 第一天后,罗斯被杀,乔伊出现。
- 第二天后,雷切尔被杀,菲比出现。
- 第三天后,菲比被杀,莫妮卡出现。
- 第四天后,莫妮卡被杀,钱德出现。