[CTSC2011] 字符串重排

题目描述

对于两个字符串 $A=a_1a_2\cdots a_n$ 和 $B=b_1b_2\cdots b_m$，定义它们的最长公共前缀长度 $\operatorname{lcp}(A,B)$ 为：

$$\operatorname{lcp}(A,B)=\max\{k\mid 0\le k\le \min(n,m),\ a_1a_2\cdots a_k=b_1b_2\cdots b_k\}.$$

给定 $n$ 个由小写英文字母组成的、两两不同的非空字符串 $S_1,S_2,\ldots,S_n$。

对于一个 $1$ 到 $n$ 的排列 $P=(p_1,p_2,\ldots,p_n)$，定义其价值为

$$W(P)=\sum_{i=2}^{n}\left(\operatorname{lcp}(S_{p_{i-1}},S_{p_i})\right)^2.$$

记所有排列中能够取得的最大价值为 $W_{\max}$。

此外，还有 $q$ 个附加任务。对于第 $i$ 个任务，给定两个不同的整数 $X_i,Y_i$。

对于一个满足 $W(P)=W_{\max}$ 的排列 $P$，如果字符串 $S_{X_i}$ 恰好排在字符串 $S_{Y_i}$ 的前一个位置，即

$$\operatorname{pos}_P(X_i)+1=\operatorname{pos}_P(Y_i),$$

则称第 $i$ 个任务被满足，并获得 $2^i$ 的奖励。其中 $\operatorname{pos}_P(x)$ 表示编号为 $x$ 的字符串在排列 $P$ 中的位置。

一个排列的总任务奖励定义为它所满足的所有任务的奖励之和。

在所有满足 $W(P)=W_{\max}$ 的排列中，考虑总任务奖励最大的排列。由于每个任务的奖励均为不同的 $2$ 的幂，因此最大总任务奖励所对应的任务集合是唯一的。

请你求出：

1. 最大价值 $W_{\max}$；
2. 最大总任务奖励所对应的所有被满足任务的编号。

输入格式

第一行包含两个整数 $n,q$，分别表示字符串数量和附加任务数量。

接下来 $n$ 行，第 $i$ 行包含一个字符串 $S_i$。

接下来 $q$ 行，第 $i$ 行包含两个整数 $X_i,Y_i$，表示第 $i$ 个附加任务。

输出格式

输出三行。

第一行输出一个非负整数 $W_{\max}$。

第二行输出一个整数 $k$，表示最大总任务奖励方案中被满足的任务数量。

第三行输出 $k$ 个整数，按照从小到大的顺序输出这些任务的编号，相邻编号之间用一个空格隔开。

如果 $k=0$，第三行输出一个空行。

样例 #1

样例输入 #1

4 6
a
b
abc
bc
1 2
1 3
3 1
4 2
2 4
2 4

样例输出 #1

2
4
1 3 5 6

样例说明

最大可能价值为 $2$。

在所有价值等于 $2$ 的排列中，可以取得的最大总任务奖励对应任务 $1,3,5,6$。例如排列 $3,1,2,4$ 可以同时满足这四个任务。

注意：题目不要求输出具体排列。

数据范围

• 对于 $10\%$ 的数据，$n\le 10$，$q=1$，每个字符串长度不超过 $50$；
• 对于 $20\%$ 的数据，$n\le 50$，$q=1$，每个字符串长度不超过 $50$；
• 对于 $50\%$ 的数据，$n,q\le 1000$，每个字符串长度不超过 $1000$；
• 对于 $70\%$ 的数据，任意字符串都不是其他任何一个字符串的前缀；
• 对于 $100\%$ 的数据，$n\le 4\times 10^4$，$q\le 10^5$，每个字符串长度不超过 $10^4$，所有字符串长度之和不超过 $2\times 10^5$。

所有字符串均由小写英文字母组成且两两不同；每个任务中 $X_i\ne Y_i$。