http://hihocoder.com/contest/hiho78/problem/1 the problem is a Trie Tree problem,which is from HihoWeek 78,named Shortest proper prefix.

if N is 10000,which is the maximum input of N in this problem.In the worst case,how many nodes the final Trie Tree is supposed to have?How to think of this problem?