Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.
Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if the user whose password is abc
inputs one of the strings abc
, abcd
or imaabcnema
, the system will successfully log him in, whereas the login will fail for axbc
.
Mihael wants to know how many ordered pairs of different users exist such that the first user, using their own password, can login as the second user.
Input Specification
The first line of input contains the positive integer
, the number of users. Each of the following
lines contains the user passwords. The passwords consist of at least one and at most 10 lowercase letters of the English alphabet.
Output Specification
The first and only line of output must contain the number of ordered pairs from the task.
Scoring
In test cases worth 40 points total, it will hold .
Sample Input 1
3
aaa
aa
abb
Sample Output 1
1
Sample Input 2
3
x
x
xy
Sample Output 2
4
Explanation for Sample Output 2
The first user can login as the second user, the second user can login as the first, and the third user can login as both the first and the second user.
Sample Input 3
5
mir
mirta
ta
ir
t
Sample Output 3
6
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This problem has now been solved in Java. The best submission takes ~0.4 seconds in the worst case.