Swap Free
시간 제한1초메모리 제한512 MB
서로 애너그램이고 글자가 중복되지 않는 n개의 단어가 주어질 때, 한 쌍의 글자만 바꿔서 서로 변환되는 단어가 없는 최대 부분집합의 크기를 구한다.
문제
단어 집합이 swap free라는 것은, 집합 안의 어떤 단어를 같은 집합 안의 다른 단어로 바꾸는 방법이 (꼭 인접하지 않아도 되는) 한 쌍의 글자를 한 번 교환하는 것만으로는 존재하지 않는다는 뜻이다.
서로 애너그램인 n개의 단어 집합이 주어진다. 어떤 단어에도 중복되는 글자는 없다. 주어진 집합의 가장 큰 swap free 부분집합의 크기를 구하라. 주어진 집합 자체가 가장 큰 swap free 부분집합일 수도 있다.
입력
첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 500)
다음 n개의 줄에 각각 단어 w가 하나씩 주어진다. (1 ≤ |w| ≤ 26)
모든 단어는 알파벳 소문자로만 이루어져 있고 중복되는 글자가 없다. n개의 단어는 모두 서로 다르며, 어떤 단어든 다른 모든 단어의 애너그램이다.
출력
가장 큰 swap free 부분집합의 크기를 정수 하나로 출력한다.