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:][: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')

ZGVmIGYocyk6CiBxLFM9WycnXSxbXTtUPXMuc3RhcnRzd2l0aAogZm9yIGMgaW4gcToKICBmb3IgSSBpbiByYW5nZSg2MCk6CiAgIGZvciBDIGluW2NbOn5JfC0yXSsoaTo9J2FudGFwZWFzcGFzc2JhdGJlZWJvYWNhdGNvZGNvd2RhYmRvZ2VlbGVsa2VtdWZseWZveGdudWhvZ2lkZWpheWtlYWtvYmtvaW9sbW93bHBpZ3JhdHJheXlhaydbSS8vMiozOl1bOjNdKV0rW2MraVtJJTIrMTpdXSooYz4nJyk6CiAgICBpZiBDPT1zOnJldHVybiAxCiAgICBpZiBUKENbOi0xXSkrVChDWzotMl0pYW5kfi0oQyBpbiBTKTpxKz1DLDtTKz1DLAogICAgIApzID0gIiIiCmFudApvd2wKYmFzcwpwcmlkZQpib2JjYXQKcGVhZm93bAplbGVwaGFudApoZWRnZWhvZ3MKY3JvY29kaWxlCmFudGlkZW1vY3JhdAphc3BpZG9nYW5vaWRlaQpiaW9kZWdyYWRhYmlsaXR5CmFuZ2lvZWxlcGhhbnRpYXNpcwpwcm9wcmVhbnRlcGVudWx0aW1hdGUKIiIiCnMxID0gIiIiCmEKb3gKcmFtCmJlYXIKa29hbGEKYW50ZWxvcGUKYWxiYXRyb3NzCnpvb2tlZXBlcgpzYWxhbWFuZGVyCmNhdGVycGlsbGFyCmhpcHBvcG90YW11cwoiIiIKZm9yIGkgaW4gZmlsdGVyKE5vbmUscy5zcGxpdCgnXG4nKSk6Cglhc3NlcnQgZihpKSBpcyBub3QgTm9uZQoKZm9yIGkgaW4gZmlsdGVyKE5vbmUsczEuc3BsaXQoJ1xuJykpOgoJYXNzZXJ0IGYoaSkgaXMgTm9uZQoKcHJpbnQoJ3Rlc3RzIHBhc3NlZCcp