시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB53151025.641%

문제

결정적 유한 오토마타(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
W3sicHJvYmxlbV9pZCI6IjM1OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJERkEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNiMFx1YzgxNVx1YzgwMSBcdWM3MjBcdWQ1NWMgXHVjNjI0XHVkMWEwXHViOWM4XHVkMGMwKERGQSlcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJhNDBcdWQyZjBcdWFkZjhcdWI3OThcdWQ1MDRcdWI4NWMgXHVjODE1XHVjODEwXHVjNzQwIFx1YzBjMVx1ZDBkYywgXHVhYzA0XHVjMTIwXHVjNzQwIFx1YzgwNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBERkFcdWM3NTggXHVjODA0XHVjNzc0XHVjNWQwXHViMjk0IFx1YWUwMFx1Yzc5MCBcdWQ1NThcdWIwOThcdWFjMDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGMxXHVkMGRjIHNcdWM2NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUwMFx1Yzc5MCBsXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgbFx1Yzc3NCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHVjNzNjXHViYTc0XHVjMTFjIHNcdWI5N2MgXHViNWEwXHViMDk4XHViMjk0IFx1YzgwNFx1Yzc3NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkRGQVx1YzVkMFx1YjI5NCBcdWMyZGNcdWM3OTEgXHVjMGMxXHVkMGRjXHVhYzAwIFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWFjZTAsIFx1Y2Q1Y1x1Yzg4NSBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWNkNWNcdWM4ODUgXHVjMGMxXHVkMGRjXHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWJkODBcdWJkODQgXHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0LiBERkFcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzViOFx1YzViNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViOTdjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjMmRjXHVjNzkxIFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWM1YjRcdWI1YTQgXHVjZDVjXHVjODg1IFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjIFx1YzBjMVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjNzIwXHVkNTVjXHVhYzFjXHVjNzc4IFx1YzViOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTRcdWJhNzQsIFx1ZDU2ZFx1YzBjMSBcdWM3NzQgXHVjNWI4XHVjNWI0XHVjNzU4IERGQVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBmaXgsIGZvbywgb3hcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzViOFx1YzViNFx1Yjk3YyBERkFcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzQgREZBXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWNkMWQgN1x1YWMxY1x1YWMwMCBcdWM3ODhcdWFjZTAgXHVjMGMxXHVkMGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjMGMxXHVkMGRjXHVjNzU4IFx1YzIxOFx1YWMwMCA1XHVhYzFjXHVjNzc0XHVhY2UwIFx1Yzc3NCBcdWM1YjhcdWM1YjRcdWI5N2MgNVx1YWMxY1x1YmNmNFx1YjJlNCBcdWM4MDFcdWM3NDAgXHVjMGMxXHVkMGRjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RmYS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzBweDsgd2lkdGg6NDIwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzViOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjNWI4XHVjNWI0XHVjNzU4IERGQVx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTdcdWIxMjQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyA1MDAwKSBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDMwXHVjNzc0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNWI4XHVjNWI0XHVjNzU4IERGQVx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFuZ3VhZ2UgUmVjb2duaXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkRldGVybWluaXN0aWMgRmluYWwtU3RhdGUgQXV0b21hdG9uIChERkEpIGlzIGEgZGlyZWN0ZWQgbXVsdGlncmFwaCB3aG9zZSB2ZXJ0aWNlcyBhcmUgY2FsbGVkIHN0YXRlcyBhbmQgZWRnZXMgYXJlIGNhbGxlZCB0cmFuc2l0aW9ucy4gRWFjaCBERkEgdHJhbnNpdGlvbiBpcyBsYWJlbGVkIHdpdGggYSBzaW5nbGUgbGV0dGVyLiBNb3Jlb3ZlciwgZm9yIGVhY2ggc3RhdGUgcyBhbmQgZWFjaCBsZXR0ZXIgbCB0aGVyZSBpcyBhdCBtb3N0IG9uZSB0cmFuc2l0aW9uIHRoYXQgbGVhdmVzIHMgYW5kIGlzIGxhYmVsZWQgd2l0aCBsLiBERkEgaGFzIGEgc2luZ2xlIHN0YXJ0aW5nIHN0YXRlIGFuZCBhIHN1YnNldCBvZiBmaW5hbCBzdGF0ZXMuIERGQSBkZWZpbmVzIGEgbGFuZ3VhZ2Ugb2YgYWxsIHdvcmRzIHRoYXQgY2FuIGJlIGNvbnN0cnVjdGVkIGJ5IHdyaXRpbmcgZG93biB0aGUgbGV0dGVycyBvbiBhIHBhdGggZnJvbSB0aGUgc3RhcnRpbmcgc3RhdGUgdG8gc29tZSBmaW5hbCBzdGF0ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBsYW5ndWFnZSB3aXRoIGEgZmluaXRlIHNldCBvZiB3b3JkcyBpdCBpcyBhbHdheXMgcG9zc2libGUgdG8gY29uc3RydWN0IGEgREZBIHRoYXQgZGVmaW5lcyB0aGlzIGxhbmd1YWdlLiBUaGUgcGljdHVyZSBvbiB0aGUgbGVmdCBzaG93cyBzdWNoIERGQSBmb3IgdGhlIGxhbmd1YWdlIGNvc2lzdGluZyBvZiB0aHJlZSB3b3JkczogZml4LCBmb28sIG94LiBIb3dldmVyLCB0aGlzIERGQSBoYXMgNyBzdGF0ZXMsIHdoaWNoIGlzIG5vdCBvcHRpbWFsLiBUaGUgREZBIG9uIHRoZSByaWdodCBkZWZpbmVzIHRoZSBzYW1lIGxhbmd1YWdlIHdpdGgganVzdCA1IHN0YXRlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kZmEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMwcHg7IHdpZHRoOjQyMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGF0ZXMgaW4gYSBERkEgdGhhdCBkZWZpbmVzIHRoZSBnaXZlbiBsYW5ndWFnZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBudW1iZXIgbiAoMSAmbGU7IG4gJmxlOyA1IDAwMCkgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBsYW5ndWFnZS4gSXQgaXMgZm9sbG93ZWQgYnkgbiBsaW5lcyB3aXRoIGEgd29yZCBvbiBlYWNoIGxpbmUuIEVhY2ggd29yZCBjb25zaXN0cyBvZiAxIHRvIDMwIGxvd2VyY2FzZSBMYXRpbiBsZXR0ZXJzIGZyb20gJmxkcXVvO2EmcmRxdW87IHRvICZsZHF1bzt6JnJkcXVvOy4gQWxsIHdvcmRzIGluIHRoZSBpbnB1dCBcdWZiMDFsZSBhcmUgZGlcdWZiMDBlcmVudC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0byB0aGUgb3V0cHV0IFx1ZmIwMWxlIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyICZtZGFzaDsgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHN0YXRlcyBpbiBhIERGQSB0aGF0IGRlXHVmYjAxbmVzIHRoZSBsYW5ndWFnZSBmcm9tIHRoZSBpbnB1dCBcdWZiMDFsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2007 L번