이진 트리의 3색 칠하기

트리는 하나의 노드와, 그 노드에 연결된 몇 개(0개, 1개 또는 2개)의 서브트리로 이루어진다. 이 서브트리들을 자식(children)이라고 부른다.

트리의 명세(specification)는 숫자들의 나열이다. 트리의 자식 수가:

• 0개이면, 명세는 원소가 0 하나뿐인 나열이다.
• 1개이면, 명세는 1로 시작하고 그 뒤에 자식의 명세가 이어진다.
• 2개이면, 명세는 2로 시작하고 그 뒤에 첫 번째 자식의 명세, 이어서 두 번째 자식의 명세가 온다.

트리의 모든 정점은 빨강, 초록, 파랑 중 하나로 칠해야 한다. 단, 다음 규칙을 지켜야 한다.

• 정점과 그 자식은 같은 색일 수 없다.
• 한 정점에 자식이 둘 있으면, 두 자식은 서로 다른 색이어야 한다.

이때 초록으로 칠할 수 있는 정점은 최대 몇 개이고 최소 몇 개인가?

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 트리의 명세를 읽는다.
• 초록으로 칠할 수 있는 정점 수의 최댓값과 최솟값을 계산한다.
• 결과를 표준 출력에 쓴다.

표준 입력의 첫 번째이자 유일한 줄에 트리의 명세인 한 단어가 주어진다. 이 단어의 길이는 10000자를 넘지 않는다.

표준 출력의 첫 번째이자 유일한 줄에 정수 두 개를 공백 하나로 구분해 출력한다. 각각 초록으로 칠할 수 있는 정점 수의 최댓값과 최솟값이다.