提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1022 三色二叉树

Accept: 253    Submit: 771
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列,我们称之为“二叉树序列S”:

例如,下图所表示的二叉树可以用二叉树序列S=21200110来表示。

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

Input

输入数据由多组数据组成。
每组数据仅有一行,不超过10000个字符,表示一个二叉树序列。

Output

对于每组输入数据,输出仅一行包含两个整数,依次表示最多和最少有多少个点能够被染成绿色。

Sample Input

1122002010

Sample Output

5 2

Submit  Back  Status  Discuss