#P40001. 2019 ICPC NCNA Regional Contest B - Code Names

2019 ICPC NCNA Regional Contest B - Code Names

题目描述

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⊆W is called “swap-free” if there is no way to turn a word x∈S into another word y∈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≤N≤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