손상된 이진 탐색 트리

컴퓨터의 메모리는 항상 완벽하게 신뢰할 수 있는 것은 아니다. 제조 결함, 정전, 잡음이나 고온 같은 환경 요인 때문에 메모리 워드의 내용이 손상될 수 있으며, 이러한 오류는 계산에 심각한 영향을 줄 수 있다.

예를 들어 검색을 빠르게 하려고 실수(real number) 키를 저장하는 이진 탐색 트리(BST) 를 유지한다고 하자. BST는 키가 $x$인 임의의 노드에 대해 다음 성질을 만족하는 이진 트리이다.

1. 왼쪽 서브트리에는 키가 $x$보다 작은 노드만 있다.
2. 오른쪽 서브트리에는 키가 $x$보다 큰 노드만 있다.
3. 왼쪽과 오른쪽 서브트리도 모두 BST이다.
4. 중복된 키는 허용되지 않는다.

아래 그림의 왼쪽은 크기가 9인 BST이다. 메모리 오류로 키 $11$이 $7$로 손상되면(오른쪽 그림), 트리는 더 이상 올바른 BST가 아니며 일부 성질이 깨진다. 이렇게 손상된 트리에서 $9$를 검색하면 잘못된 경로를 따라가 잘못된 답을 반환한다.

트리를 올바르게 유지하기 위해 주기적으로 트리를 점검하고, 올바르지 않으면 고칠 수 있다. 간단한 방법 하나는 몇몇 노드를 골라(반드시 키가 손상된 노드일 필요는 없다) 그 키를 적절한 값으로 바꾸어 다시 올바른 BST로 만드는 것이다. 트리의 모양은 바뀌지 않으며, 오직 키만 수정하고 새 키는 임의의 실수가 될 수 있다.

바꾸는 키의 수를 최소로 하고 싶으므로, 주어진 트리를 올바른 BST로 만들기 위해 키를 바꾸어야 하는 노드의 최소 개수 를 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 하나의 BST를 나타낸다.

각 테스트 케이스의 첫 줄에는 트리의 노드 개수인 정수 $n$ ($n \le 50000$)이 주어진다. 이어지는 $n - 1$개의 줄에는 각각 한 노드를 나타내는 세 항목이 공백으로 구분되어 주어진다. 순서대로 그 노드에 저장된 키, 그 노드의 부모에 저장된 키, 그리고 그 노드가 부모의 왼쪽 자식이면 L, 오른쪽 자식이면 R인 문자이다.

모든 키는 $10^6$ 이하의 서로 다른 음이 아닌 정수이다(다만 올바른 BST의 키는 일반적으로 실수일 수 있다). 루트는 어떤 줄에서도 자식으로 나타나지 않는 유일한 노드이므로, $n = 1$인 트리는 노드를 나타내는 줄이 하나도 없다.

입력의 끝은 $0$ 하나만 있는 줄로 표시된다.

각 테스트 케이스마다, 주어진 트리를 올바른 BST로 만들기 위해 바꾸어야 하는 키의 최소 개수를 한 줄에 출력한다.