P16287 [Lanqiao Cup 2026 NOI Qualifier Python Group A] Word Merging

Xiaolan has $n$ pairwise distinct words $s_1, s_2, \dots, s_n$ in the dictionary. Each word consists only of lowercase letters, and its length does not exceed $20$. Xiaolan defines an operation: perform exactly one of the following two transformations on a word: - Insert one lowercase letter at any position. - Delete any one letter from it. Except for the inserted or deleted position, the relative order of the original letters remains unchanged. Now, please count how many ordered word pairs $(s_i, s_j)$ (where $i \ne j$) satisfy: $s_i$ can be transformed into $s_j$ by performing exactly one operation as defined above.

The first line contains a positive integer $n$. The next $n$ lines each contain a string consisting only of lowercase letters, representing a word.

Output one line containing one integer, representing the number of ordered word pairs that satisfy the condition.

### Sample Explanation The $8$ ordered word pairs that satisfy the condition are: - $(aab, ab)$: delete the $1$st letter $a$ from $aab$ to get $ab$. - $(ab, aab)$: insert the letter $a$ at the $1$st position of $ab$ to get $aab$. - $(ab, a)$: delete the $2$nd letter $b$ from $ab$ to get $a$. - $(a, ab)$: insert the letter $b$ at the $2$nd position of $a$ to get $ab$. - $(ab, b)$: delete the $1$st letter $a$ from $ab$ to get $b$. - $(b, ab)$: insert the letter $a$ at the $1$st position of $b$ to get $ab$. - $(bb, b)$: delete the $1$st letter $b$ from $bb$ to get $b$. - $(b, bb)$: insert the letter $b$ at the $1$st position of $b$ to get $bb$. ### Constraints For $30\%$ of the testdata, $1 \leq n \leq 100$. For all testdata, $1 \leq n \leq 10000$. It is guaranteed that all words are pairwise distinct. Translated by ChatGPT 5