题目描述

给定 $n$ 个无序字母对。字母区分大小写；“无序”表示一个字母对中的两个字母可以交换位置。

请构造一个由 $n+1$ 个字母组成的字符串，使得输入中的每个字母对都恰好对应字符串中一组相邻字母。若有多种方案，输出字典序最小的字符串；若无法构造，输出 NoSolution。

输入格式

第一行输入正整数 $n$。接下来 $n$ 行，每行输入两个字母，表示一个无序字母对。

输出格式

若存在满足要求的字符串，输出字典序最小者；否则输出 NoSolution。

数据范围与约定

$2\le n\le1500$；字母为 ASCII 字母，区分大小写，两个字母之间可能出现多次。

可见测试数据

输入数据 1

12
cc
cc
cD
cA
Cc
AE
cb
cB
cC
Dc
bc
Ec

输出数据 1

BcAEcCcDcbccc

输入数据 2

2
AB
CD

输出数据 2

NoSolution

输入数据 3

10
Bd
dA
CB
Ea
BC
eB
ee
AE
aC
ee

输出数据 3

CBCaEAdBeee