Problem E
Gotta Catch 'Em Twice
Ash Ketchum has finally managed to win the Pokémon World Championship - it took him 25 years, but he finally did it.
Now, at the age of 10, it’s finally time for him to retire... or so he wishes - there’s still one last test, as he needs to prove his worth to the infamous Professor Oak.
The Professor Oak wants to see if Ash managed to collect two copies of the same Pokémon, to examine them. Ash is sure that he has at least a duplicate among his huge collection of Pokémon, but due to his latest celebrations for the victory, all of his pokeballs fell and got mixed up on the floor.
He has a list of $N$ words, each of them being the name of the Pokémon species contained in one of the pokeballs. He wants to bring with him the minimum number of pokeballs such that he will be guaranteed to have two Pokémon of the same species, to pass Professor Oak’s test.
What’s the minimum number of pokeballs he needs to take with him?
Input
The first line contains one integer: $N$, the number of pokeballs.
Each of the next $N$ lines contain a lower case string, $S_ i$, a Pokémon species contained in one of the pokeballs.
Output
You need to write a single line containing a single integer: the answer to the problem.
Constraints
-
$1 \le N \le 5000$.
-
Each Pokémon species is between 5 and 20 characters long.
-
It’s always guaranteed that there’s at least a duplicate species among Ash’s Pokémons.
Example
In the first example below, Ash needs to take 4 of the pokeballs, as if he only takes 3 he could end up with "bulbasaur", "eevee" and "pikachu", which are all different.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 bulbasaur pikachu eevee pikachu bulbasaur |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 magikarp magikarp magikarp magikarp magikarp magikarp magikarp |
2 |
