← 返回题目列表

Codeforces · 508/D

D. 坦尼娅和密码

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

当爸爸在工作时,小女孩塔尼娅决定使用爸爸的秘密数据库密码。爸爸的密码是一个由n+2个字符组成的字符串。她把密码所有可能的n个三字母连续子串写在纸上,每张纸一个,然后把密码扔了出去。每个三个字母的子字符串都会写入它在密码中出现的次数。因此,Tanya 最终得到了 n 张纸。

然后 Tanya 意识到爸爸会因为了解她的游戏而感到不安,并决定恢复密码或至少恢复与最终一组三字母字符串相对应的任何字符串。你必须帮助她完成这项艰巨的任务。我们知道爸爸的密码是由拉丁字母的大小写字母和数字组成。拉丁字母的大写和小写字母被认为是不同的。

输入

第一行包含整数n (1 ≤ n ≤ 2·105),即Tanya 得到的三字母子串的数量。

接下来的 n 行每行包含三个字母,构成爸爸密码的子字符串。输入中的每个字符都是小写或大写拉丁字母或数字。

输出

如果 Tanya 在游戏过程中的某个地方犯了错误,并且与给定子字符串集对应的字符串不存在,则打印“NO”。

如果可以恢复与给定子字符串集相对应的字符串,请打印“YES”,然后打印任何合适的密码选项。

示例

输入 #1

5
aca
aba
aba
cab
bac

输出 #1

YES
abacaba

输入 #2

4
abc
bCb
cb1
b13

输出 #2

NO

输入 #3

7
aaa
aaa
aaa
aaa
aaa
aaa
aaa

输出 #3

YES
aaaaaaaaa