Polycarp 想要组装自己的键盘。多行布局对他来说太复杂了——他的键盘将只包含一行,其中所有 $$$26$$$ 小写拉丁字母将按某种顺序排列。
Polycarp 在他注册的所有网站上使用相同的密码 $$$s$$$ (这很糟糕,但他不在乎)。他想组装一个键盘,可以很容易地输入这个密码。他不喜欢在输入密码时移动手指,因此,对于 $$$s$$$ 中的每一对相邻字符,它们在键盘上应该是相邻的。例如,如果密码是 abacaba,则布局 cabdefghi... 是完美的,因为字符 a 和 c 在键盘上相邻,并且 a 和 b 在键盘上相邻。保证$$$s$$$中不存在两个相邻的相等字符,因此,例如password不能是password(两个字符s相邻)。
如果可能的话,您能帮助 Polycarp 选择完美的键盘布局吗?
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 1000$$$) — 测试用例的数量。
接下来是 $$$T$$$ 行,每一行包含一个表示测试用例的字符串 $$$s$$$ ($$$1 \le |s| \le 200$$$)。 $$$s$$$ 仅由小写拉丁字母组成。 $$$s$$$ 中不存在两个相邻的相同字符。
输出
对于每个测试用例,执行以下操作:
- 如果不可能组装一个完美的键盘,打印NO(大写,在这个问题中很重要);
- 否则,打印 YES(大写),然后打印由 $$$26$$$ 小写拉丁字母组成的字符串 - 完美的布局。每个拉丁字母应该在此字符串中恰好出现一次。如果有多个答案,请打印其中任何一个。
示例
输入 #1
5 ababa codedoca abcda zxzytyz abcdefghijklmnopqrstuvwxyza
输出 #1
YES bacdefghijklmnopqrstuvwxyz YES edocabfghijklmnpqrstuvwxyz NO YES xzytabcdefghijklmnopqrsuvw NO