시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

You are given $W$, a set of $N$ words that are anagrams of each other. There are no duplicate letters in any word. A set of words $S \subseteq W$ is called "swap-free" if there is no way to turn a word $x \in S$ into another word $y \in S$ by swapping only a single pair of (not necessarily adjacent) letters in $x$. Find the size of the largest swap-free set $S$ chosen from the given set $W$.

입력

The first line of input contains an integer $N$ ($1 \le N \le 500$). Following that are $N$ lines each with a single word. Every word contains only lowercase English letters and no duplicate letters. All $N$ words are unique, have at least one letter, and every word is an anagram of every other word.

출력

Output the size of the largest swap-free set.

예제 입력 1

6
abc
acb
cab
cba
bac
bca

예제 출력 1

3

예제 입력 2

11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers

예제 출력 2

8

예제 입력 3

6
ates
east
eats
etas
sate
teas

예제 출력 3

4