Given a binary tree represented by a sequence , which consists of only characters 0
, 1
, and 2
. The sequence is the preorder traversal sequence of the binary tree, where:
0
represents a node with 0 child.1
represents a node with 1 child.2
represents a node with 2 children.
For example, the binary tree in the following picture is represented by .
Given the binary tree, you need to color this binary tree with three different colors: red, green, and blue. The requirements are:
- Every node must have a different color from its children.
- If a node has two children, the two children must have different colors.
Given the binary tree sequence , find the maximum possible number of nodes and the minimum possible number of nodes colored in red.
Input Specification
The first line of input contains one string (), indicating the sequence of the binary tree.
Output Specification
Output two integers in one line, the maximum possible number of nodes and the minimum possible number of nodes colored in red.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints |
Sample Input 1
2210010
Sample Output 1
4 1
Explanation
The binary tree is shown in the above picture. To get the maximum possible number of nodes colored in red, we can color nodes , , , in red. To get the minimum possible number of nodes colored in red, we can color the node in red.
Sample Input 2
1122002010
Sample Output 2
5 2
Comments