UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2932. [Poi1999]树的染色问题

Statistics 下载数据

Description

一棵二叉树采用以下规则描述:
1.如果一个节点度数为0,则仅用一个元素“0”来描述它。
2.如果一个节点度数为1,则对它的描述以“1”开头,后面接着对它的孩子的描述。
3.如果一个节点度数为2,则对它的描述以“2”开头,后面接着的首先是它的左孩子的描述,然后是右孩子的描述。
在树中每一个节点必须被着为红色、绿色或蓝色。然而,我们必须遵循如下规定:
1.根点和它的孩子不能有相同的颜色。
2.如果一个节点有两个孩子,那么这两个节点必定有两个不同的颜色。
有多少个节点可以被着为绿色呢?
任务
写一个程序:
1.读取对一棵树的描述。
2.计算可以被着为绿色的节点的最大值和最小值。
3.把结果输出

Input

 
首行是由一个字符串组成(不长于10000字符),它是对一棵树的描述。

Output

首行两个用空格隔开的整数,它们分别表示可以被着为绿色的节点的最大和最小数目。

Sample Input

1122002010

Sample Output

5 2

Hint

Source