← 返回题目列表

Codeforces · 776/A

A. 连环杀手

中文机器翻译题面 查看原题

我们敬爱的侦探夏洛克目前正在努力抓捕一名每天杀人的连环杀手。利用他的推理能力,他了解到凶手有一个选择下一个受害者的策略。

凶手在第一天从两名潜在受害者开始,选择这两名受害者中的一个,杀死选定的受害者并用一个新人取代他。他每天都重复这个过程。这样,他每天就有两个潜在的受害者可供选择。 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

注意

在第一个示例中,凶手从罗斯和雷切尔开始。

- 第一天后,罗斯被杀,乔伊出现。
- 第二天后,雷切尔被杀,菲比出现。
- 第三天后,菲比被杀,莫妮卡出现。
- 第四天后,莫妮卡被杀,钱德出现。