题目描述
对于两个字符串 A=a1a2⋯an 和 B=b1b2⋯bm,定义其最长公共前缀长度 LCP(A,B) 如下:
LCP(A,B)=max{k∣0≤k≤n,k≤m,a1a2⋯ak=b1b2⋯bk}
给定 n 个由小写字母组成的两两不同的非空字符串 S1,S2,⋯,Sn,对于一个 1 到 n 的排列 P=(p1,p2,⋯,pn),定义 P 的价值 W(P) 如下:
W(P)=i=2∑n(LCP(Spi−1,Spi))2
我们设能够产生最大价值的排列为 PG∗。
此外,还有 q 个附加任务。对于第 i 个任务,给定两个 1 到 n 之间的不同的整数 Xi 和 Yi。对于排列 P,若 P 在满足 W(P)=W(PG∗) 的前提条件之下,同时满足第 Xi 个字符串 SXi 恰好排在第 Yi 个字符串 SYi 之前, 即 pos(SXi)+1=pos(SYi),其中 pos(Si) 表示字符串 Si 在排列中的位置,则排列 P 还将获得 2i 的奖励。所有任务的奖励之和称之为总任务奖励。
我们设能够使得总任务奖励最大的排列为 PB∗。
试求:
- W(PG∗),即可能产生的最大价值;
- PB∗,在保证最大价值前提下,可以使总任务奖励最大的排列。
输入格式
第一行包含两个整数 n 和 q,表示字符串和附加任务的数量,中间用一个空格隔开;
接下来 n 行,描述字符串,其中第 i 行包含一个字符串 Si;
接下来 q 行,描述附加任务,其中第 i 行包含两个整数 Xi 和 Yi,中间用一个空格隔开。
输出格式
包含三行。
第一行包含一个非负整数 W(PG∗);
第二行若干个数,每两个数之间用一个空格隔开,这一行第一个数表示满足附加任务的数量 k,接下来 k 个数为这些任务的序号,序号从 1 开始,按从小到大的顺序输出;
第三行包含 n 个用一个空格隔开的正整数,表示一个 1 到 n 的排列 PB∗。
样例
4 6
a
b
abc
bc
1 2
1 3
3 1
4 2
2 4
2 4
2
4 1 3 5 6
3 1 2 4
数据范围与提示
评分标准
对于一个测试点:
- 如果输出文件的第一行正确可以得到 2 分;
- 如果输出文件的第二行正确可以得到 4 分;
- 如果输出文件的第三行正确可以得到 4 分;
- 如果输出文件的两行都正确则可以得到 10 分。
对于第三问中的排列,如果存在多个解, 则输出任意一个解均可得分。
若某问无法完成,也请按照格式输出,以避免测评失败。
数据范围
对于 10% 的数据,n≤10,q=1,每个字符串的长度不超过 50;
对于 20% 的数据,n≤50,q=1,每个字符串的长度不超过 50;
对于 50% 的数据,n,q≤1000,每个字符串的长度不超过 1000;
对于 70% 的数据,任意字符串不为其他任何一个字符串的前缀;
对于 100% 的数据,n≤4×104,q≤105, 每个字符串的长度不超过 104,所有字符串的长度和不超过 2×105。