a = input()
class Node():
def __init__(self, value, depth=0):
self.value = value
self.left = self.right = None
self.depth = depth
def insert(self, value):
if value <= self.value:
if self.left == None:
self.left = Node(value, self.depth+1)
# print(f'{value} is the left child of {self.value}')
else:
self.left.insert(value)
if value > self.value:
if self.right == None:
self.right = Node(value, self.depth+1)
# print(f'{value} is the right child of {self.value}')
else:
self.right.insert(value)
def children(self):
children = 0
if self.left != None: children += 1
if self.right != None: children += 1
return children
def match(self, other):
if self.left == None and self.right == None:
return True
if other.left == None and self.left != None:
return False
if other.right == None and self.right != None:
return False
if self.left == None:
return self.right.match(other.right)
if self.right == None:
return self.left.match(other.left)
return self.left.match(other.left) and self.right.match(other.right)
def traverse(self):
# print(self.value, self.left, self.right)
yield self
if self.left != None:
yield from self.left.traverse()
if self.right != None:
yield from self.right.traverse()
A = Node(a[0])
for c in a[1:]:
A.insert(c)
leaf = external = external_path = internal_path = depth = 0
for node in A.traverse():
if node.children() == 0:
leaf += 1
external += 2
external_path += 2*(node.depth+1)
if node.children() == 1:
external += 1
external_path += node.depth+1
internal_path += node.depth
depth = max(node.depth, depth)
print(depth, leaf, external, internal_path, external_path)
