Three-Coloring of Binary Trees

A tree consists of one node and some (zero, one, or two) subtrees connected to it. These subtrees are called its children.

A specification of a tree is a sequence of digits. If the number of children of the tree is:

• zero, the specification is a sequence with the single element 0;
• one, the specification begins with 1, followed by the specification of the child;
• two, the specification begins with 2, followed by the specification of the first child and then the specification of the second child.

Every vertex of the tree must be painted red, green, or blue, subject to the following rules:

• a vertex and its child cannot have the same color;
• if a vertex has two children, the two children must have different colors.

At most and at least how many vertices can be painted green?

Write a program that:

• reads the specification of the tree from standard input,
• computes the maximum and the minimum number of vertices that can be painted green,
• writes the results to standard output.

The first and only line of standard input contains one word (no longer than 10000 characters), which is a specification of a tree.

Print on the first and only line of standard output exactly two integers separated by a single space: the maximum and the minimum number of vertices that can be painted green, in that order.