def f(s):
 q,S=[''],[];T=s.startswith
 for c in q:
  for I in range(30):
   for j in range(1,3):
    for C in[c[:-j]+(i:='antapeaspassbatbeeboacatcodcowdabdogeelelkemuflyfoxgnuhogidejaykeakobkoiolmowlpigratrayyak'[I*3:I*3+3])]+[c+i[j:]]*(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')

ZGVmIGYocyk6CiBxLFM9WycnXSxbXTtUPXMuc3RhcnRzd2l0aAogZm9yIGMgaW4gcToKICBmb3IgSSBpbiByYW5nZSgzMCk6CiAgIGZvciBqIGluIHJhbmdlKDEsMyk6CiAgICBmb3IgQyBpbltjWzotal0rKGk6PSdhbnRhcGVhc3Bhc3NiYXRiZWVib2FjYXRjb2Rjb3dkYWJkb2dlZWxlbGtlbXVmbHlmb3hnbnVob2dpZGVqYXlrZWFrb2Jrb2lvbG1vd2xwaWdyYXRyYXl5YWsnW0kqMzpJKjMrM10pXStbYytpW2o6XV0qKGM+JycpOgogICAgIGlmIEM9PXM6cmV0dXJuIDEKICAgICBpZiBUKENbOi0xXSkrVChDWzotMl0pYW5kfi0oQyBpbiBTKTpxKz1DLDtTKz1DLAogICAgIApzID0gIiIiCmFudApvd2wKYmFzcwpwcmlkZQpib2JjYXQKcGVhZm93bAplbGVwaGFudApoZWRnZWhvZ3MKY3JvY29kaWxlCmFudGlkZW1vY3JhdAphc3BpZG9nYW5vaWRlaQpiaW9kZWdyYWRhYmlsaXR5CmFuZ2lvZWxlcGhhbnRpYXNpcwpwcm9wcmVhbnRlcGVudWx0aW1hdGUKIiIiCnMxID0gIiIiCmEKb3gKcmFtCmJlYXIKa29hbGEKYW50ZWxvcGUKYWxiYXRyb3NzCnpvb2tlZXBlcgpzYWxhbWFuZGVyCmNhdGVycGlsbGFyCmhpcHBvcG90YW11cwoiIiIKZm9yIGkgaW4gZmlsdGVyKE5vbmUscy5zcGxpdCgnXG4nKSk6Cglhc3NlcnQgZihpKSBpcyBub3QgTm9uZQoKZm9yIGkgaW4gZmlsdGVyKE5vbmUsczEuc3BsaXQoJ1xuJykpOgoJYXNzZXJ0IGYoaSkgaXMgTm9uZQoKcHJpbnQoJ3Rlc3RzIHBhc3NlZCcp