#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000005;
int trie[MAX][27]; // 0-25: litery, 26: koniec słowa
int uni = 2; // 1 = korzeń
int ile = 0; // liczba liści
pair<int,int> dfs(int v, int depth)
{
vector<int> ends;
int cost = 0;
for(int c = 0; c < 26; ++c)
{
if (trie[v][c] == 0) continue;
auto res = dfs(trie[v][c], depth + 1);
cost += res.first;
ends.push_back(res.second);
}
// liść — słowo końcowe
if (ends.empty())
{
ile++;
return {depth, depth};
}
sort(ends.begin(), ends.end());
// dla wszystkich poza najgłębszym liściem
// sprawdzamy, czy opłaca się teleportować zamiast wracać
for (int i = 0; i + 1 < (int)ends.size(); ++i)
{
int backCost = ends[i] - depth; // cofanie
int teleportCost = 1; // powrót do korzenia
if (teleportCost < backCost)
cost -= backCost - teleportCost;
}
return {cost, ends.back()};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string slo;
for(int i = 0; i < n; ++i)
{
int gdzie = 1;
cin >> slo;
for(char ch : slo)
{
int c = ch - 'a';
if(trie[gdzie][c] == 0)
trie[gdzie][c] = uni++;
gdzie = trie[gdzie][c];
}
trie[gdzie][26]++; // koniec słowa
}
auto wynik = dfs(1, 0);
cout << "Minimalny koszt przejścia: " << wynik.first + n + n - ile << "\n";
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTUFYID0gMTAwMDAwNTsKaW50IHRyaWVbTUFYXVsyN107IC8vIDAtMjU6IGxpdGVyeSwgMjY6IGtvbmllYyBzxYJvd2EKaW50IHVuaSA9IDI7ICAgICAgIC8vIDEgPSBrb3J6ZcWECmludCBpbGUgPSAwOyAgICAgICAvLyBsaWN6YmEgbGnFm2NpCgpwYWlyPGludCxpbnQ+IGRmcyhpbnQgdiwgaW50IGRlcHRoKQp7CiAgICB2ZWN0b3I8aW50PiBlbmRzOwogICAgaW50IGNvc3QgPSAwOwoKICAgIGZvcihpbnQgYyA9IDA7IGMgPCAyNjsgKytjKQogICAgewogICAgICAgIGlmICh0cmllW3ZdW2NdID09IDApIGNvbnRpbnVlOwogICAgICAgIGF1dG8gcmVzID0gZGZzKHRyaWVbdl1bY10sIGRlcHRoICsgMSk7CiAgICAgICAgY29zdCArPSByZXMuZmlyc3Q7CiAgICAgICAgZW5kcy5wdXNoX2JhY2socmVzLnNlY29uZCk7CiAgICB9CgogICAgLy8gbGnFm8SHIOKAlCBzxYJvd28ga2/FhGNvd2UKICAgIGlmIChlbmRzLmVtcHR5KCkpCiAgICB7CiAgICAgICAgaWxlKys7CiAgICAgICAgcmV0dXJuIHtkZXB0aCwgZGVwdGh9OwogICAgfQoKICAgIHNvcnQoZW5kcy5iZWdpbigpLCBlbmRzLmVuZCgpKTsKCiAgICAvLyBkbGEgd3N6eXN0a2ljaCBwb3phIG5hamfFgsSZYnN6eW0gbGnFm2NpZW0KICAgIC8vIHNwcmF3ZHphbXksIGN6eSBvcMWCYWNhIHNpxJkgdGVsZXBvcnRvd2HEhyB6YW1pYXN0IHdyYWNhxIcKICAgIGZvciAoaW50IGkgPSAwOyBpICsgMSA8IChpbnQpZW5kcy5zaXplKCk7ICsraSkKICAgIHsKICAgICAgICBpbnQgYmFja0Nvc3QgPSBlbmRzW2ldIC0gZGVwdGg7IC8vIGNvZmFuaWUKICAgICAgICBpbnQgdGVsZXBvcnRDb3N0ID0gMTsgICAgICAgICAgIC8vIHBvd3LDs3QgZG8ga29yemVuaWEKICAgICAgICBpZiAodGVsZXBvcnRDb3N0IDwgYmFja0Nvc3QpCiAgICAgICAgICAgIGNvc3QgLT0gYmFja0Nvc3QgLSB0ZWxlcG9ydENvc3Q7CiAgICB9CgogICAgcmV0dXJuIHtjb3N0LCBlbmRzLmJhY2soKX07Cn0KCmludCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsKCiAgICBpbnQgbjsKICAgIGNpbiA+PiBuOwogICAgc3RyaW5nIHNsbzsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgewogICAgICAgIGludCBnZHppZSA9IDE7CiAgICAgICAgY2luID4+IHNsbzsKICAgICAgICBmb3IoY2hhciBjaCA6IHNsbykKICAgICAgICB7CiAgICAgICAgICAgIGludCBjID0gY2ggLSAnYSc7CiAgICAgICAgICAgIGlmKHRyaWVbZ2R6aWVdW2NdID09IDApCiAgICAgICAgICAgICAgICB0cmllW2dkemllXVtjXSA9IHVuaSsrOwogICAgICAgICAgICBnZHppZSA9IHRyaWVbZ2R6aWVdW2NdOwogICAgICAgIH0KICAgICAgICB0cmllW2dkemllXVsyNl0rKzsgLy8ga29uaWVjIHPFgm93YQogICAgfQoKICAgIGF1dG8gd3luaWsgPSBkZnMoMSwgMCk7CiAgICBjb3V0IDw8ICJNaW5pbWFsbnkga29zenQgcHJ6ZWrFm2NpYTogIiA8PCB3eW5pay5maXJzdCArIG4gKyBuIC0gaWxlIDw8ICJcbiI7Cn0K
MzkKYWFhY2JiY2JiY2JjYmFiYmFhYmNjYWFiYWFhYmJhYgphYWJhYWFhYWFhYWNiCmFhYmNiYWNjY2NjYWNiYWJhY2JjYmNhYWJjYmNhY2NhY2JiY2FiY2NjYmNjYWFhY2EKYWFjYmFiYmFhYgphYmJhYWJjYWNiY2NiY2NiYWJiYmJiYWFiY2FhYWNhYWJhYWFjYmNiYmFjYWJjYmNiYWFiCmFiY2NhYmJiY2NhYWNjY2NhYmFjYWFjY2FhY2JhY2NhYWFjYmNhYWJiYwphY2JhYWNiY2FhY2NiYmJhY2NjYmNhY2FiY2NjYmNjYWFjYWFhYmFjYWJjYWJjY2NiYmJjY2FiYWFiYmJhYWFiY2FiYWJhYWNhY2NjY2FjCmFjYmFiY2JhY2NhYWJhYmNhYmNjYWNjYmFjYmNiYWJhYmJiY2JhYmJhYmNjY2JhYWNiYmJjYmJiYWNiYmFhYmFjY2FiY2JjY2FjYWFjYWNhYmFiYWFjY2NiY2JhY2NjY2NjYwphY2JhYmNiY2JjYmJiYmFjYmJiYWFiY2JjYmNjYmFhYWNhYmNiYWFiY2FhYmJhCmFjY2JhYWJhY2NhYmJhY2FhY2NiY2JhYWNjYmFjY2FhYWFjYmNhYmNjYWNiYWFhYWNiYmNhYWFiYWMKYWNjYmNiYmFiYWNjYWFiYWNhY2FjYmFhYmJjY2NjYmFjYWFjY2JhYWNhY2NjYmFjYWJhYWNiYmNjYmJiY2JjYWJiYmFhYWFhYWJhYWJjY2MKYgpiYQpiYWJhY2JhY2NiY2NiY2FjYmNiYmFhYWNiY2NiY2JiY2FhYWFhYWJhY2JhY2NiY2FhY2JiY2JjYmNjYmNjYWNiY2JhYWJiYmNiY2NiY2JiYWNhYmFhYmNhYmNhYmJjYWIKYmFiYmNjYmEKYmFiY2JhYmJjYWNjY2JhY2JiYQpiYWJjY2NiYmJhY2FiYWFiYWJiYWNjYmJjYWNjY2JhY2NiYmNiY2FjY2JiYmFiYmNiY2IKYmFjYmFhYmJjY2NjYmNhYmNiYWNiYmFiYWFhYmNjYmJiYmJjYWNhYWNiYWJhY2NhY2FhYmNiYmJjYmFhY2JhYWFhYWNiYmNjCmJiYWJhY2FiYWJhYmJhYWNjYWFhYmFhYmFiY2NhYmJiY2JhYWFjYWJjYWJhY2FhY2JhYWFiYWJhYWJiYmNiYWNiYmFiY2JjYmNhY2NjYWJiY2JiYwpiYmFjYmJiYmNhYmJhY2JjYmNjYWJiYWNjYmFjY2NiY2FjYmNjYWNjY2FhY2FjYmNjYmJjY2JjY2NhYmJhYWJjYWFhY2NhYmNjY2NiY2JjYmFiY2NiYmFhYWFiY2EKYmJiY2JjY2JjCmJiYmNiY2NjYgpiYmNjY2FhYWJhY2FiYWNjY2NjY2NiYmFjY2FjY2JhYWJhY2FiYWNhY2FjYWJiYWMKYmNhYWFhY2NhYmFjY2FjYWFiY2NhY2NjYmJjYWJhYWNiY2FjYmJhYWFiY2NjYWJiYmNiYWNjYmFjY2JhYmFiY2FiY2NhYWFjY2FhYWFiYmFiCmJjYWJhYWNhYmFiYmNiYWJjYWJhY2FiYmFhY2JiY2JhYWNiY2NhYWNhYmNjYWNjYWJiYWJjYmJiYWJjY2FiYmJhYWFhYmNiYWFjYWFiYmFjYmJjY2JhYWNhYWNjY2JiY2JiYgpiY2NiYWJiYWNhY2JjYWNjY2JiY2NjY2JjYmJjY2NiYWJjY2JiY2NjYmFiY2JiYQpiY2NiYWJiYmNhYWJhY2NhYmNhYmJiYWJjYWNhYWJhYmFjYmNiYWNjYWNhY2FhYmNjYWJjY2FjYWJjYmJiYWNhYWNiY2FjYmMKYmNjYmNhYmFiY2JjYgpiY2NiY2FjYWFjYWNjYmIKY2FhY2NjYWNiY2JiYWIKY2FjYWFhYmNhY2NiY2JjY2JjY2FhYWFjYmFiYWNjY2FiYmNjY2NjY2FiYWJiYmNiYWFiY2FjY2NjY2NhYmNiY2NhYWJjYWJhYmNhY2JiYWJiY2NjCmNhY2NhYWNhY2FiYWJiYmNjYmJhY2FjYWFhYmJhY2NjYWFiY2JiYWNiYmNjYWNjYmFiYmNjYmJjYmNjYmJjYWJjY2JjY2JjYmFjY2FjYWNhY2JiYmFjY2JjY2JjYmNhCmNiYWJiY2NiYmJhYmFiY2FhY2NiYWFhYWFjYWNjYmJhYQpjYmNhY2NiY2JiCmNjYmFjYmFjYmNjYmNjYWFhYmJjYmNhYmJjYWNjY2FhYWJiYmNjYmNjY2FiYmJhY2JjYWFhYmNiYWJjYmJiY2NjY2FjY2FjYWJiYmJjYmNiY2NjYmJiYWNhYgpjY2NhYmNhYmJhYmFiYWFiYWNhYmFiYWNhYmJjY2FjY2NiY2JiY2NhYWJiY2FjY2NiY2NiYWFjCmNjY2FjY2NiYWJhYmFiYWNhYWJhYmNhYmNhY2JhYmNiYmFhYmNhY2JiY2NiYWFhY2NjYWNiYmJiY2JjYmNjYmNiYWJhYmFiYQpjY2NiYmFjYmFjY2NjY2FiYmJhYmFjY2FjYmFiYmFiYWIKY2NjYmJiYmFiY2NhYmFiYWNiYWNjYWFiY2FhYWNjY2NiYmFjY2JhYmFhYWNjY2FhYmJiYmFjYWFhCg==
39
aaacbbcbbcbcbabbaabccaabaaabbab
aabaaaaaaaacb
aabcbacccccacbabacbcbcaabcbcaccacbbcabcccbccaaaca
aacbabbaab
abbaabcacbccbccbabbbbbaabcaaacaabaaacbcbbacabcbcbaab
abccabbbccaaccccabacaaccaacbaccaaacbcaabbc
acbaacbcaaccbbbacccbcacabcccbccaacaaabacabcabcccbbbccabaabbbaaabcababaacaccccac
acbabcbaccaababcabccaccbacbcbababbbcbabbabcccbaacbbbcbbbacbbaabaccabcbccacaacacababaacccbcbaccccccc
acbabcbcbcbbbbacbbbaabcbcbccbaaacabcbaabcaabba
accbaabaccabbacaaccbcbaaccbaccaaaacbcabccacbaaaacbbcaaabac
accbcbbabaccaabacacacbaabbccccbacaaccbaacacccbacabaacbbccbbbcbcabbbaaaaaabaabccc
b
ba
babacbaccbccbcacbcbbaaacbccbcbbcaaaaaabacbaccbcaacbbcbcbccbccacbcbaabbbcbccbcbbacabaabcabcabbcab
babbccba
babcbabbcacccbacbba
babcccbbbacabaababbaccbbcacccbaccbbcbcaccbbbabbcbcb
bacbaabbccccbcabcbacbbabaaabccbbbbbcacaacbabaccacaabcbbbcbaacbaaaaacbbcc
bbabacabababbaaccaaabaababccabbbcbaaacabcabacaacbaaababaabbbcbacbbabcbcbcacccabbcbbc
bbacbbbbcabbacbcbccabbaccbacccbcacbccacccaacacbccbbccbcccabbaabcaaaccabccccbcbcbabccbbaaaabca
bbbcbccbc
bbbcbcccb
bbcccaaabacabacccccccbbaccaccbaabacabacacacabbac
bcaaaaccabaccacaabccacccbbcabaacbcacbbaaabcccabbbcbaccbaccbababcabccaaaccaaaabbab
bcabaacababbcbabcabacabbaacbbcbaacbccaacabccaccabbabcbbbabccabbbaaaabcbaacaabbacbbccbaacaacccbbcbbb
bccbabbacacbcacccbbccccbcbbcccbabccbbcccbabcbba
bccbabbbcaabaccabcabbbabcacaababacbcbaccacacaabccabccacabcbbbacaacbcacbc
bccbcababcbcb
bccbcacaacaccbb
caacccacbcbbab
cacaaabcaccbcbccbccaaaacbabacccabbccccccababbbcbaabcaccccccabcbccaabcababcacbbabbccc
caccaacacababbbccbbacacaaabbacccaabcbbacbbccaccbabbccbbcbccbbcabccbccbcbaccacacacbbbaccbccbcbca
cbabbccbbbababcaaccbaaaaacaccbbaa
cbcaccbcbb
ccbacbacbccbccaaabbcbcabbcacccaaabbbccbcccabbbacbcaaabcbabcbbbccccaccacabbbbcbcbcccbbbacab
cccabcabbababaabacababacabbccacccbcbbccaabbcacccbccbaac
cccacccbabababacaababcabcacbabcbbaabcacbbccbaaacccacbbbbcbcbccbcbabababa
cccbbacbacccccabbbabaccacbabbabab
cccbbbbabccababacbaccaabcaaaccccbbaccbabaaacccaabbbbacaaa