← 返回题目列表

Codeforces · 1618/B

B. 缺少二元组

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

波利卡普想出了一个新游戏来和你玩。他称之为“缺失的二元组”。

单词的二元组是其中两个相邻字母的序列。

例如,单词“abbaaba”包含二元词“ab”、“bb”、“ba”、“aa”、“ab”和“ba”。

游戏进行如下。首先,波利卡普想出了一个仅由小写字母“a”和“b”组成的单词。然后,他按照单词中出现的顺序将所有双字母写在白板上。然后,他从白板上擦掉其中一张。

最后,坡旅甲邀请你猜猜他想出的词是什么。

你的目标是找到任何一个单词,这样就可以写下它的所有二元组并删除其中一个,以便得到的二元组序列与波利卡普最终得到的序列相同。

测试的生成方式使得答案存在。如果有多个答案,您可以打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$) — Polycarp 提出的单词的长度。

每个测试用例的第二行包含该单词的 $$$n-2$$$ 双字母组,以单个空格分隔。每个二字母组由两个字母组成,每个字母要么是“a”,要么是“b”。

对输入的附加约束:至少存在一个字符串,以便可以写下除一个之外的所有二元组,从而得到的序列与输入中的序列相同。换句话说,答案是存在的。

输出

对于每个测试用例打印一个单词,由 $$$n$$$ 字母组成,每个字母应该是 'a' 或 'b'。应该可以写下它的所有二元组并删除其中一个,以便得到的二元组序列与波利卡普最终得到的二元组序列相同。

测试的生成方式使得答案存在。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

4
7
ab bb ba aa ba
7
ab ba aa ab ba
3
aa
5
bb ab bb

输出 #1

abbaaba
abaabaa
baa
bbabb

注意

该示例中的前两个测试用例是由单词“abbaaba”生成的。正如声明中所列出的,它包含二元组“ab”、“bb”、“ba”、“aa”、“ab”和“ba”。

在第一个测试用例中,第 $$$5$$$ 个二元组被删除。

在第二个测试用例中,$$$2$$$-nd 二元组被删除。然而,该序列也可能是由单词“abaabaa”产生的。它包含二元组“ab”、“ba”、“aa”、“ab”、“ba”和“aa”。缺少的二元组是第 $$$6$$$ 个。

在第三个测试用例中,“baa”、“aab”和“aaa”都是有效答案。