The Labyrinth of Wells

Deep inside Bytemountain lies a mythical labyrinth of wells. Its entrance sits at the very top of the mountain, and the labyrinth is built from many rooms. Every room is painted one of three colors: red, green, or blue. Two rooms of the same color look exactly alike and cannot be told apart.

Each room holds three wells, numbered $1$, $2$, and $3$. The only way to move between rooms is to jump into a well: from an upper room you fall (not necessarily straight down) into the room at the bottom of that well. Every other room can be reached from the entrance room, and every path through the labyrinth eventually leads to the dragon's lair at the very bottom. One trip through the labyrinth is described by the sequence of well numbers chosen in the rooms you visit, one after another; such a sequence is called a journey plan.

The Bytedragon lives in the lair. Legend says that whoever presents the complete map of the labyrinth to the dragon receives an enormous treasure, while everyone else is kicked out of the mountain by a mighty stomp of the dragon's foot.

A hero named Bytezar has walked the labyrinth many times and drawn his own map. The Bytedragon told him that although every room does appear on the map, many of them appear more than once.

"I once drew a similar picture," said the Bytedragon, patting Bytezar on the shoulder, "but I soon noticed that even after building fewer rooms, a visitor following any journey plan would still see the very same sequence of room colors. So I thought for a while and shrank the map as much as possible."

Write a program that reads Bytezar's map from standard input, determines the true number of rooms in the labyrinth, and prints that number to standard output.

The first line contains a single integer $n$ ($2 \le n \le 6000$), the number of rooms including the dragon's lair. Rooms are numbered from $1$ to $n$ so that a larger number means a lower room: the entrance room is number $1$ and the dragon's lair is number $n$.

Each of the next $n - 1$ lines describes one room (every room except the dragon's lair) together with the wells leading down from it. A line contains a letter, one space, and three integers separated by single spaces. The letter gives the room's color (C for red, Z for green, N for blue), and the $i$-th integer (for $i = 1, 2, 3$) is the number of the room that well $i$ leads to. Every well leads to a room with a larger number.

Print a single integer: the minimal number of rooms, including the dragon's lair, of a labyrinth equivalent to the one given in the input. Two labyrinths are equivalent when a traveller who follows any journey plan observes the same sequence of room colors in both.