Perfect Keyboard

题意翻译

给出一个字符串$S$，求是否存在一种$26$个字母排列的构造方式$T$使得$S$中任意相邻两位都在$T$中相邻，数据保证$S$不会存在相邻两位字母相同，若存在则输出$YES$并输出一种合法的构造方式，否则输出$NO$。

题目描述

Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $ 26 $ lowercase Latin letters will be arranged in some order. Polycarp uses the same password $ s $ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $ s $ , they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $ s $ , so, for example, the password cannot be password (two characters s are adjacent). Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?

输入输出格式

输入格式

The first line contains one integer $ T $ ( $ 1 \le T \le 1000 $ ) — the number of test cases. Then $ T $ lines follow, each containing one string $ s $ ( $ 1 \le |s| \le 200 $ ) representing the test case. $ s $ consists of lowercase Latin letters only. There are no two adjacent equal characters in $ s $ .

输出格式

For each test case, do the following: - if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem); - otherwise, print YES (in upper case), and then a string consisting of $ 26 $ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

输出样例 #1

YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO