쥐라기 유해

시베리아의 고생물학자들이 최근 쥐라기 공룡 골격의 조각을 여러 개 발굴하여 고생물학 박물관으로 보내려고 한다. 공룡이 워낙 거대해서 조각을 한꺼번에 담을 수 있는 상자가 없었기 때문에, 골격을 낱개의 뼈로 분리한 뒤 박물관에서 다시 조립하기로 했다. 조립을 쉽게 하려고, 두 뼈가 서로 붙어 있던 각 관절 자리에 라벨을 붙여 두었다.

포장하는 동안 여분의 뼈가 몇 개 더 발견되어 같은 꾸러미에 함께 담아 보냈다.

꾸러미가 박물관에 도착하자 두 가지 문제가 드러났다.

• 라벨이 모두 다르지는 않다. 라벨에는 대문자 A부터 Z까지만 쓰였다. 서로 이어져야 하는 두 관절은 항상 같은 글자를 갖지만, 같은 글자를 가진 관절 쌍이 여러 개 있을 수 있다.
• 여분의 뼈에도 같은 종류의 라벨이 붙어 있어서, 어떤 관절은 다른 관절과 이어질 필요가 없다. 다행히 하나의 뼈에서는 각 글자가 최대 한 관절에만 나타난다.

박물관이 골격 조각 하나를 복원하도록 도와라. 다음 조건을 모두 만족하도록 서로 이을 수 있는 뼈들의 집합을 골라야 한다.

• 두 관절은 같은 라벨을 가질 때만 이을 수 있다.
• 고른 각 뼈에 대해, 그 뼈에서 라벨이 붙은 모든 관절은 다른 어떤 관절과 이어져야 한다.
• 고른 뼈의 개수는 가능한 한 많아야 한다.

두 뼈는 여러 관절을 통해 동시에 이어질 수도 있다.

첫 줄에 정수 $N$ --- 뼈의 개수 ($1 \le N \le 24$) 가 주어진다. 다음 $N$개의 줄에는 각각 뼈가 하나씩 주어지며, 그 뼈의 관절에 붙은 라벨을 나타내는, 서로 다른 대문자로 이루어진 비어 있지 않은 문자열이다.

골격 조각 하나를 복원하는 데 함께 쓸 수 있는 뼈의 최대 개수 $L$을 정수 하나로 출력한다. 쓸 수 있는 뼈가 없으면 $0$을 출력한다.