Maximizing Permutation Value with Bonus Tasks

Given n distinct non-empty strings composed of lowercase letters: \(S_1, S_2, \dots, S_n\). For any two strings \(A = a_1a_2\cdots a_{|A|}\) and \(B = b_1b_2\cdots b_{|B|}\), define their longest common prefix length as

[ \text{lcp}(A,B)=\max{k;|;0\le k\le \min(|A|,|B|) \text{ and } a_1a_2\cdots a_k=b_1b_2\cdots b_k} ]

For any permutation \(P=(p_1,p_2,\dots,p_n)\) of \(\{1,2,\dots,n\}\), define its value as

[ W(P)=\sum_{i=2}^{n}\Big(\text{lcp}(S_{p_{i-1}},S_{p_i})\Big)^2. ]

Let \(P^*_G\) be a permutation yielding the maximum possible \(W(P)\). In addition, there are \(q\) bonus tasks. For the \(i^\text{th}\) bonus task, two distinct integers \(X_i\) and \(Y_i\) (each between 1 and \(n\)) are given. For a permutation \(P\) satisfying \(W(P)=W(P^*_G)\), if string \(S_{X_i}\) appears immediately before string \(S_{Y_i}\) (i.e. if pos(S_{X_i})+1 = pos(S_{Y_i}), where pos(S_i) is the position of string \(S_i\) in \(P\)), then the permutation receives an extra reward of \(2^i\). The total bonus is the sum of the rewards from all bonus tasks.

Your task is to:

1. Compute \(W(P^*_G)\), the maximum possible value.
2. Among all permutations achieving \(W(P^*_G)\), choose one with the maximum total bonus reward. Let this permutation be denoted \(P^*_B\).

Note: If there are multiple optimal permutations achieving the same maximum value and bonus reward, any one of them is acceptable.

inputFormat

The input begins with two integers \(n\) and \(q\) on the first line, where \(1 \le n \le 15\) (assumed small for this problem) and \(q \ge 0\) is the number of bonus tasks.

Then follow \(n\) lines, each containing a non-empty string consisting of lowercase letters.

Then follow \(q\) lines, each containing two distinct integers \(X_i\) and \(Y_i\) (with \(1 \le X_i,Y_i \le n\)), representing a bonus task.

outputFormat

On the first line, output \(W(P^*_G)\) – the maximum possible value.

On the second line, output \(n\) space‐separated integers denoting the permutation \(P^*_B\) (i.e. the sequence of indices of strings) that achieves the maximum value and maximum bonus reward.

sample

3 1
ab
ac
ad
1 3

2
1 3 2

</p>