시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 4 3 30.000%

문제

결정적 유한 오토마타(DFA)는 방향성이 있는 멀티그래프로 정점은 상태, 간선은 전이라고 부른다.

모든 DFA의 전이에는 글자 하나가 붙여져 있다. 또, 각각의 상태 s와 각각의 글자 l에 대해서, l이 붙여져 있으면서 s를 떠나는 전이의 개수는 최대 한 개이다.

DFA에는 시작 상태가 하나 있고, 최종 상태가 있다. 최종 상태는 상태의 부분 집합이다. DFA는 어떤 언어의 모든 단어를 정의할 수 있다. 이 때, 모든 단어는 시작 상태에서 어떤 최종 상태로 가는 경로 상에 써 있는 글자이어야 한다.

단어의 개수가 유한개인 언어가 주어진다면, 항상 이 언어의 DFA를 만들 수 있다. 왼쪽 그림은 fix, foo, ox로 이루어진 언어를 DFA로 나타낸 것이다. 하지만, 이 DFA의 상태는 총 7개가 있고 상태의 개수가 가장 적은 경우가 아니다. 오른쪽 그림은 상태의 수가 5개이고 이 언어를 5개보다 적은 상태로 나타낼 수 없다.

어떤 언어가 주어졌을 때, 이 언어의 DFA를 만드늗네 필요한 상태의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 n이 주어진다. (1 ≤ n ≤ 5000) 다음 n개 줄에는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고 길이는 최대 30이다. 입력으로 주어지는 모든 단어는 서로 다르다.

출력

첫째 줄에 입력으로 주어진 언어의 DFA를 만드는데 필요한 상태의 최소 개수를 출력한다.

예제 입력 1

3
fix
foo
ox

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjM1OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJERkEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNiMFx1YzgxNVx1YzgwMSBcdWM3MjBcdWQ1NWMgXHVjNjI0XHVkMWEwXHViOWM4XHVkMGMwKERGQSlcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJhNDBcdWQyZjBcdWFkZjhcdWI3OThcdWQ1MDRcdWI4NWMgXHVjODE1XHVjODEwXHVjNzQwIFx1YzBjMVx1ZDBkYywgXHVhYzA0XHVjMTIwXHVjNzQwIFx1YzgwNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBERkFcdWM3NTggXHVjODA0XHVjNzc0XHVjNWQwXHViMjk0IFx1YWUwMFx1Yzc5MCBcdWQ1NThcdWIwOThcdWFjMDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGMxXHVkMGRjIHNcdWM2NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUwMFx1Yzc5MCBsXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgbFx1Yzc3NCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHVjNzNjXHViYTc0XHVjMTFjIHNcdWI5N2MgXHViNWEwXHViMDk4XHViMjk0IFx1YzgwNFx1Yzc3NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkRGQVx1YzVkMFx1YjI5NCBcdWMyZGNcdWM3OTEgXHVjMGMxXHVkMGRjXHVhYzAwIFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWFjZTAsIFx1Y2Q1Y1x1Yzg4NSBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWNkNWNcdWM4ODUgXHVjMGMxXHVkMGRjXHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWJkODBcdWJkODQgXHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0LiBERkFcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzViOFx1YzViNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViOTdjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViMjk0IFx1YzJkY1x1Yzc5MSBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgXHVjNWI0XHViNWE0IFx1Y2Q1Y1x1Yzg4NSBcdWMwYzFcdWQwZGNcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzcyMFx1ZDU1Y1x1YWMxY1x1Yzc3OCBcdWM1YjhcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0XHViYTc0LCBcdWQ1NmRcdWMwYzEgXHVjNzc0IFx1YzViOFx1YzViNFx1Yzc1OCBERkFcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgZml4LCBmb28sIG94XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM1YjhcdWM1YjRcdWI5N2MgREZBXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0IERGQVx1Yzc1OCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjZDFkIDdcdWFjMWNcdWFjMDAgXHVjNzg4XHVhY2UwIFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWMyMThcdWFjMDAgNVx1YWMxY1x1Yzc3NFx1YWNlMCBcdWM3NzQgXHVjNWI4XHVjNWI0XHViOTdjIDVcdWFjMWNcdWJjZjRcdWIyZTQgXHVjODAxXHVjNzQwIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kZmEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMwcHg7IHdpZHRoOjQyMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWM1YjhcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzViOFx1YzViNFx1Yzc1OCBERkFcdWI5N2MgXHViOWNjXHViNGRjXHViMjk3XHViMTI0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMwYzFcdWQwZGNcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgNTAwMCkgXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAgXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAzMFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzViOFx1YzViNFx1Yzc1OCBERkFcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMwYzFcdWQwZGNcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzU5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikxhbmd1YWdlIFJlY29nbml0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5EZXRlcm1pbmlzdGljIEZpbmFsLVN0YXRlIEF1dG9tYXRvbiAoREZBKSBpcyBhIGRpcmVjdGVkIG11bHRpZ3JhcGggd2hvc2UgdmVydGljZXMgYXJlIGNhbGxlZCBzdGF0ZXMgYW5kIGVkZ2VzIGFyZSBjYWxsZWQgdHJhbnNpdGlvbnMuIEVhY2ggREZBIHRyYW5zaXRpb24gaXMgbGFiZWxlZCB3aXRoIGEgc2luZ2xlIGxldHRlci4gTW9yZW92ZXIsIGZvciBlYWNoIHN0YXRlIHMgYW5kIGVhY2ggbGV0dGVyIGwgdGhlcmUgaXMgYXQgbW9zdCBvbmUgdHJhbnNpdGlvbiB0aGF0IGxlYXZlcyBzIGFuZCBpcyBsYWJlbGVkIHdpdGggbC4gREZBIGhhcyBhIHNpbmdsZSBzdGFydGluZyBzdGF0ZSBhbmQgYSBzdWJzZXQgb2YgZmluYWwgc3RhdGVzLiBERkEgZGVmaW5lcyBhIGxhbmd1YWdlIG9mIGFsbCB3b3JkcyB0aGF0IGNhbiBiZSBjb25zdHJ1Y3RlZCBieSB3cml0aW5nIGRvd24gdGhlIGxldHRlcnMgb24gYSBwYXRoIGZyb20gdGhlIHN0YXJ0aW5nIHN0YXRlIHRvIHNvbWUgZmluYWwgc3RhdGUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbGFuZ3VhZ2Ugd2l0aCBhIGZpbml0ZSBzZXQgb2Ygd29yZHMgaXQgaXMgYWx3YXlzIHBvc3NpYmxlIHRvIGNvbnN0cnVjdCBhIERGQSB0aGF0IGRlZmluZXMgdGhpcyBsYW5ndWFnZS4gVGhlIHBpY3R1cmUgb24gdGhlIGxlZnQgc2hvd3Mgc3VjaCBERkEgZm9yIHRoZSBsYW5ndWFnZSBjb3Npc3Rpbmcgb2YgdGhyZWUgd29yZHM6IGZpeCwgZm9vLCBveC4gSG93ZXZlciwgdGhpcyBERkEgaGFzIDcgc3RhdGVzLCB3aGljaCBpcyBub3Qgb3B0aW1hbC4gVGhlIERGQSBvbiB0aGUgcmlnaHQgZGVmaW5lcyB0aGUgc2FtZSBsYW5ndWFnZSB3aXRoIGp1c3QgNSBzdGF0ZXMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZGZhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzMHB4OyB3aWR0aDo0MjBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RhdGVzIGluIGEgREZBIHRoYXQgZGVmaW5lcyB0aGUgZ2l2ZW4gbGFuZ3VhZ2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gKDEgJmxlOyBuICZsZTsgNSAwMDApICZtZGFzaDsgdGhlIG51bWJlciBvZiB3b3JkcyBpbiB0aGUgbGFuZ3VhZ2UuIEl0IGlzIGZvbGxvd2VkIGJ5IG4gbGluZXMgd2l0aCBhIHdvcmQgb24gZWFjaCBsaW5lLiBFYWNoIHdvcmQgY29uc2lzdHMgb2YgMSB0byAzMCBsb3dlcmNhc2UgTGF0aW4gbGV0dGVycyBmcm9tICZsZHF1bzthJnJkcXVvOyB0byAmbGRxdW87eiZyZHF1bzsuIEFsbCB3b3JkcyBpbiB0aGUgaW5wdXQgXHVmYjAxbGUgYXJlIGRpXHVmYjAwZXJlbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdG8gdGhlIG91dHB1dCBcdWZiMDFsZSBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciAmbWRhc2g7IHRoZSBtaW5pbWFsIG51bWJlciBvZiBzdGF0ZXMgaW4gYSBERkEgdGhhdCBkZVx1ZmIwMW5lcyB0aGUgbGFuZ3VhZ2UgZnJvbSB0aGUgaW5wdXQgXHVmYjAxbGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d