#P12849. 最绝望的 hidesuwa

    ID: 12035 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200并查集倍增字符串数据结构2025“钉耙编程”中国大学生算法设计暑期联赛(8)

最绝望的 hidesuwa

最绝望的 hidesuwa

Problem Description

banana Ilya 龙哥请求支援 hide ~ 大虾发出绝望的最后一声 声一后最的望绝出发虾大 ~ edih 援支求请哥龙 aylI ananab 小 E 正在美美 hide,却突然发现自己掉入了回文时空,hide 之神要求他解决一个问题才能回到原本的生活。 具体来说,hide 之神的目标是:

  • 一个长度为 nn 的字符串 ss。
  • 字符串由 2626 个小写字母 a∼za\sim z 组成。
  • 有 mm 条限制,每条限制形如 [li,ri][l_i, r_i],表示 s[li..ri]s[l_i..r_i] 这个子串被要求是回文串。 你要求出满足要求的字符串个数,对 998244353998244353 取模的结果。 同时,hide 之神还非常关注 top20,你还要输出满足要求的,字典序最小的前 2020 个字符串。(数据保证至少有 2020 个不同的字符串满足要求)

Input

本题有多组测试数据。第一行一个正整数 TT,表示数据组数,接下来输入每组测试数据。 对于每组测试数据:

  • 第一行两个正整数 n,mn,m,表示目标字符串长度,以及限制个数。
  • 接下来 mm 行,每行两个正整数 [li,ri][l_i, r_i] 表示一个限制。

Output

对于每组数据:

  • 第一行输出一个非负整数,表示满足要求的字符串个数,对 998244353998244353 取模的结果。
  • 接下来 2020 行,每行一个长度为 nn 的由 2626 个小写字母构成的字符串,表示 top20。

Sample Input

1
5 1
1 5

Sample Output

17576
aaaaa
aabaa
aacaa
aadaa
aaeaa
aafaa
aagaa
aahaa
aaiaa
aajaa
aakaa
aalaa
aamaa
aanaa
aaoaa
aapaa
aaqaa
aaraa
aasaa
aataa

Hint

对于所有数据,1≤T≤10,1≤n,m≤1051\leq T\leq 10, 1\leq n, m\leq 10^5,1≤li≤ri≤n1\leq l_i\leq r_i\leq n。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(8)