Corrupted BST

Computer memory is not always fully reliable: the contents of a memory word can become corrupted because of manufacturing defects, power failures, or environmental conditions such as noise and high temperature. Such a fault can seriously affect a computation.

For example, suppose you keep a Binary Search Tree (BST) of real numbers so that searches run quickly. A BST is a binary tree in which, for every node with key $x$:

1. its left subtree contains only nodes with key less than $x$;
2. its right subtree contains only nodes with key greater than $x$;
3. both subtrees are themselves BSTs;
4. duplicate keys are not allowed.

The figure below (left) shows a BST of size 9. If the key $11$ is corrupted into $7$ (right figure), the tree is no longer a valid BST — some of the properties fail — and a search for $9$ now follows the wrong path and returns a wrong answer.

To keep the tree valid, we can inspect it periodically and repair it whenever it has become invalid. One simple repair is to choose some nodes (not necessarily the ones whose keys were corrupted) and change their keys to values that make the tree a valid BST again. The shape of the tree does not change — only keys are edited, and a new key may be any real number.

Because we want to change as few keys as possible, compute the minimum number of nodes whose keys must be changed to make the given tree a valid BST.

The input contains several test cases; each describes one BST.

The first line of a test case contains a single integer $n$ ($n \le 50000$), the number of nodes in the tree. Each of the next $n - 1$ lines describes one node with three space-separated items: the key stored at the node, the key stored at its parent, and a single character — L if the node is the left child of its parent, or R if it is the right child.

All keys are non-negative integers no larger than $10^6$ and are pairwise distinct (although, in general, the keys of a valid BST may be real numbers). The root is the only node that never appears as a child, so a tree with $n = 1$ is described by no node lines.

The input terminates with a line containing a single $0$.

For each test case, print a single line containing the minimum number of key changes needed to turn the given tree into a valid BST.