def f(s):
 q,S=[''],[];T=s.startswith
 for c in q:
  for I in range(60):
   for C in[c[:~I|-2]+(i:='antapeaspassbatbeeboacatcodcowdabdogeelelkemuflyfoxgnuhogidejaykeakobkoiolmowlpigratrayyak'[I//2*3:I//2*3+3])]+[c+i[I%2+1:]]*(c>''):
    if C==s:return 1
    if T(C[:-1])+T(C[:-2])and~-(C in S):q+=C,;S+=C,
 
s = """
ant
owl
bass
pride
bobcat
peafowl
elephant
hedgehogs
crocodile
antidemocrat
aspidoganoidei
biodegradability
angioelephantiasis
propreantepenultimate
"""
s1 = """
a
ox
ram
bear
koala
antelope
albatross
zookeeper
salamander
caterpillar
hippopotamus
"""
for i in filter(None,s.split('\n')):
	assert f(i) is not None
 
for i in filter(None,s1.split('\n')):
	assert f(i) is None
 
print('tests passed')

ZGVmIGYocyk6CiBxLFM9WycnXSxbXTtUPXMuc3RhcnRzd2l0aAogZm9yIGMgaW4gcToKICBmb3IgSSBpbiByYW5nZSg2MCk6CiAgIGZvciBDIGluW2NbOn5JfC0yXSsoaTo9J2FudGFwZWFzcGFzc2JhdGJlZWJvYWNhdGNvZGNvd2RhYmRvZ2VlbGVsa2VtdWZseWZveGdudWhvZ2lkZWpheWtlYWtvYmtvaW9sbW93bHBpZ3JhdHJheXlhaydbSS8vMiozOkkvLzIqMyszXSldK1tjK2lbSSUyKzE6XV0qKGM+JycpOgogICAgaWYgQz09czpyZXR1cm4gMQogICAgaWYgVChDWzotMV0pK1QoQ1s6LTJdKWFuZH4tKEMgaW4gUyk6cSs9Qyw7Uys9QywKICAgICAKcyA9ICIiIgphbnQKb3dsCmJhc3MKcHJpZGUKYm9iY2F0CnBlYWZvd2wKZWxlcGhhbnQKaGVkZ2Vob2dzCmNyb2NvZGlsZQphbnRpZGVtb2NyYXQKYXNwaWRvZ2Fub2lkZWkKYmlvZGVncmFkYWJpbGl0eQphbmdpb2VsZXBoYW50aWFzaXMKcHJvcHJlYW50ZXBlbnVsdGltYXRlCiIiIgpzMSA9ICIiIgphCm94CnJhbQpiZWFyCmtvYWxhCmFudGVsb3BlCmFsYmF0cm9zcwp6b29rZWVwZXIKc2FsYW1hbmRlcgpjYXRlcnBpbGxhcgpoaXBwb3BvdGFtdXMKIiIiCmZvciBpIGluIGZpbHRlcihOb25lLHMuc3BsaXQoJ1xuJykpOgoJYXNzZXJ0IGYoaSkgaXMgbm90IE5vbmUKCmZvciBpIGluIGZpbHRlcihOb25lLHMxLnNwbGl0KCdcbicpKToKCWFzc2VydCBmKGkpIGlzIE5vbmUKCnByaW50KCd0ZXN0cyBwYXNzZWQnKQ==