#P18685. Recover the String

Recover the String

Recover the String

题目描述

有一个只包含小写英文字母的字符串 ss。小青鱼很喜欢它,于是记下了它的所有不同的非空子串,并在它们之间连有向边。具体地,对于两个不同的子串 s1,s2s_1,s_2,如果存在一个字母 cc,使得 s2=s1+cs_2=s_1+c 或 s2=c+s1s_2=c+s_1,他就从 s1s_1 向 s2s_2 连一条有向边。之后,他删除了所有重复的边。这样就得到了一张有向无环图(DAG)。

不幸的是,小青鱼忘记了原字符串 ss,甚至也不记得图上的每个顶点对应哪个子串。现在只剩下这张图,请帮助他恢复原字符串。因为可能存在多个可行字符串,他只希望得到其中字典序最小的一个。

这里“子串”指原串中连续的一段;相同的子串即使出现多次,在图中也只有一个顶点。边的方向为短子串到多一个字符的长子串;同一条边只保留一次。空串不是输入图的顶点。

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

每组测试用例的第一行包含两个整数 n,mn,m(1≤n≤1061\le n\le10^6,0≤m≤2×1060\le m\le2\times10^6),表示顶点数和边数。

接下来 mm 行,第 ii 行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示一条从 uiu_i 到 viv_i 的有向边。保证至少存在一个可行的字符串。

保证所有测试用例的 nn 之和不超过 10610^6,mm 之和不超过 2×1062\times10^6。

输出格式

对每组测试用例输出一行,一个只包含小写英文字母的字符串,表示字典序最小的可行答案。

样例输入

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:

第二组原图:aba 的全部不同子串及边

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

第三组原图:aaba 的全部不同子串及边