oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

passwords Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Statement

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!

Input

The first line of input contains a single integer, n.

The next n lines of input each contain a string si.

Output

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.

Limits

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.

Sample Input

5
dunjudge
judge
nope
hack
hack

Sample Output

2

Notes

Please do not actually try to use this method to gain access to people's accounts. It doesn't work.

Tags

Graph Theory, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
140121s256MBMinimum
260221s256MBMinimum
3011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o passwords -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.