Description

For two strings $A = a_1a_2\dots a_n$ and $B = b_1b_2\dots b_m$, define their longest common prefix length $LCP(A, B)$ as follows: $LCP(A, B) = \max\{k \mid 0 \le k \le n, k \le m, a_1a_2\dots a_k = b_1b_2\dots b_k\}$

Given $n$ distinct non-empty strings $S_1, S_2, \dots, S_n$ consisting of lowercase letters, for a permutation $P = (p_1, p_2, \dots, p_n)$ of $1$ to $n$, define the value $W(P)$ of $P$ as follows: $$W(P) = \sum_{i=2}^{n} (LCP(S_{p_{i-1}}, S_{p_i}))^2$$

Let $P_G^*$ be a permutation that produces the maximum value.

Additionally, there are $q$ additional tasks. For the $i$-th task, two distinct integers $X_i$ and $Y_i$ between $1$ and $n$ are given. For a permutation $P$, if $P$ satisfies the condition $W(P) = W(P_G^*)$, and simultaneously satisfies that the $X_i$-th string $S_{X_i}$ is placed exactly before the $Y_i$-th string $S_{Y_i}$, i.e., $pos(S_{X_i}) + 1 = pos(S_{Y_i})$, where $pos(S_i)$ denotes the position of string $S_i$ in the permutation, then the permutation $P$ receives a reward of $2^i$. The sum of rewards for all tasks is called the total task reward.

Let $P_B^*$ be a permutation that maximizes the total task reward.

Find: (1) $W(P_G^*)$, the maximum possible value. (2) $P_B^*$, a permutation that maximizes the total task reward while ensuring the maximum value $W(P_G^*)$ is achieved.

Input

The first line contains two integers $n$ and $q$, representing the number of strings and the number of additional tasks, separated by a space. The next $n$ lines describe the strings, where the $i$-th line contains a string $S_i$. The next $q$ lines describe the additional tasks, where the $i$-th line contains two integers $X_i$ and $Y_i$, separated by a space.

Output

The output contains two lines. The first line contains a non-negative integer $W(P_G^*)$. The second line contains $n$ positive integers separated by spaces, representing a permutation $P_B^*$ of $1$ to $n$.

Subtasks

For a test case: If the first line of the output is correct, you get 2 points; If the second line of the output is correct, you get 8 points; If both lines of the output are correct, you get 10 points. For the permutation in the second question, if there are multiple solutions, outputting any one of them will earn the points.

Examples

Input 1

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

Output 1

2
3 1 2 4

Constraints

For 10% of the data, $n \le 10$, $q = 1$, the length of each string does not exceed 50; For 20% of the data, $n \le 50$, $q = 1$, the length of each string does not exceed 50; For 50% of the data, $n \le 1000$, $q \le 1000$, the length of each string does not exceed 1000; For 70% of the data, no string is a prefix of any other string; For 100% of the data, $n \le 40\,000$, $q \le 100\,000$, the length of each string does not exceed 10\,000; For 100% of the data, the sum of the lengths of all strings does not exceed 200\,000.