A mysterious hacker is trying to hack the dunjudge.me website! To accomplish that, he has stolen a piece of paper containing the passwords of all n accounts (including administrator's account) on dunjudge.me from the administrator.
In this parallel dimension, dunjudge passwords only allow lowercase latin letters to be used. Also, two passwords are considered equivalent if at least one of the following is satisfied:
- There is a letter which appears in both passwords.
- There is a third password which is equivalent to both passwords.
The hacker is trying to log into the administrator's account. He will only succeed if he enters a password which is equivalent to the administrator's password and is also a password used by a dunjudge account, due to some weird security exploit.
For example, if the piece of paper contains 'a', 'ab', 'b' and 'd', and the administrator's account is 'a', he will gain access if he enters any of the passwords other than 'd' as they are all equivalent.
However, the hacker is busy as he has three seasons of Gilligan's Island to binge-watch. Thus, he wants to gain access by trying the minimum number of passwords. Help him code a program to find the minimum number of attempts needed!
The first line of input contains a single integer, n.
The next n lines of input each contain a string si.
The first and only line of output should contain a single integer, denoting the minimum number of attempts needed to hack into the administrator's account.
For all subtasks, 1 ≤ n ≤ 500000 and all passwords are at most 15 characters long. Note that some passwords may be equal.
Subtask 1 (40%): n ≤ 1000
Subtask 2 (60%): There are no more constraints.
Subtask 3 (0%): Sample test cases.
Please do not actually try to use this method to gain access to people's accounts. It doesn't work.