当前没有测试数据。

三色二叉树

题目描述

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

$$S=\begin{cases}0 & \text{表示该树没有子节点}\\1S_{1} & \text{表示该树有一个节点，$S_{1}$为其子树的二叉树序列}\\2S_{1}S_{2} & \text{表示该树由两个子节点，$S_{1}$和$S_{2}$分别表示其两个子树的二叉树序列}\end{cases} $$

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

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

输入格式

输入只有一行一个字符串$s$，表示二叉树序列。

输出格式

输出只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

数据范围与提示

对于全部的测试点，保证$1 \leq |s| \leq 5 \times 10^{5}$，$s$中只含字符$0$，$1$，$2$。

样例

1122002010

5 2