#P18685. Recover the String
Recover the String
Recover the String
题目描述
有一个只包含小写英文字母的字符串 。小青鱼很喜欢它,于是记下了它的所有不同的非空子串,并在它们之间连有向边。具体地,对于两个不同的子串 ,如果存在一个字母 ,使得 或 ,他就从 向 连一条有向边。之后,他删除了所有重复的边。这样就得到了一张有向无环图(DAG)。
不幸的是,小青鱼忘记了原字符串 ,甚至也不记得图上的每个顶点对应哪个子串。现在只剩下这张图,请帮助他恢复原字符串。因为可能存在多个可行字符串,他只希望得到其中字典序最小的一个。
这里“子串”指原串中连续的一段;相同的子串即使出现多次,在图中也只有一个顶点。边的方向为短子串到多一个字符的长子串;同一条边只保留一次。空串不是输入图的顶点。
输入格式
第一行一个整数 (),表示测试用例数。
每组测试用例的第一行包含两个整数 (,),表示顶点数和边数。
接下来 行,第 行包含两个整数 (),表示一条从 到 的有向边。保证至少存在一个可行的字符串。
保证所有测试用例的 之和不超过 , 之和不超过 。
输出格式
对每组测试用例输出一行,一个只包含小写英文字母的字符串,表示字典序最小的可行答案。
样例输入
3
1 0
5 6
2 4
2 5
5 3
4 3
1 5
1 4
8 11
1 2
1 4
1 6
2 5
3 4
3 6
4 5
4 7
5 8
6 7
7 8
样例输出
a
aba
aaba
样例说明
以下图片均从原英文 PDF 直接截取,保留原顶点编号、箭头和子串标签。
第一组用例的图只有一个顶点,对应字符串 a:

第二组用例的原图和每个顶点对应的子串如下,字典序最小的原字符串为 aba:

第三组用例的原图和每个顶点对应的子串如下,字典序最小的原字符串为 aaba:
