Code Names

면접 대비

시간 제한1초메모리 제한1024 MB

요약

중복 없는 글자로 이루어진 N개의 애너그램이 주어질 때, 한 쌍의 글자만 바꿔서 서로 변환되지 않는 가장 큰 부분집합의 크기를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
6
abc
acb
cab
cba
bac
bca
```
예상 출력
```
3
```

예제 2

입력

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

예상 출력

예제 3
입력
```
6
ates
east
eats
etas
sate
teas
```
예상 출력
```
4
```