1703. [POI 2000] 管道迷宫

【题目描述】

在Byte山内部有一座神秘的管道迷宫。迷宫的入口在山顶上。迷宫由许多房间组成。每个房间都是红，绿，蓝三种颜色之一。两个颜色相同的房间看上去一模一样，无法区分。在每个房间中都有三根管道，编号为1,2，3.从一个房间到达另一个房间的办法只有一种：在上方的房间跳入一根管道，（不一定垂直地）坠入管道下方的房间。从入口出发能走到任意房间。迷宫中所有的道路都通向最底层的龙巢。在迷宫中的每一次旅行都对应着一系列数字，即依次选择的管道编号。这一系列数字被称作旅行计划。

Byte龙生活在龙巢中。传说，给出从迷宫入口到龙巢的整个旅行计划的人将得到一笔巨大的宝藏。其他人讲被Byte龙大脚踢出山脉。

一位名叫Byte扎尔的英雄走了好几次迷宫，然后他得到了旅行计划。虽然如此，Byte龙说即使所有的房间都被标注在地图上，它们中的许多却出现了不止一次。

“我画了一张类似的图，”Byte龙轻拍着Byte扎尔的肩膀说，“但不久就发现尽管我画出了较少的房间，进入迷宫的访问者仍然能看到和原来相同相同的颜色序列，无论他按照什么旅行计划走。我想了一下，决定尽可能地减少房间数。”

写一个程序，对Byte扎尔给出的地图，计算迷宫最少的房间数。

【输入格式】

第一行有一个整数n，2<=n<=6000，代表房间数量（包含龙巢）。房间从1到n编号，因此有着较大编号的房间更为靠下（入口是1，龙巢是n）。

接下来n-1行描述了迷宫中除了龙巢的每一个房间。每一行依次有一个字母，一个空格，三个空格隔开的整数。字母代表房间的颜色（红色为C，绿色为Z，蓝色为N），第i个数（i=1,2,3）是i号管道通向的房间。

【输出格式】

输出一行一个整数，即迷宫最少可能的房间数（包含龙巢），使得迷宫仍能和输入文件中描述的等价。等价意味着，无论旅行者按照何种旅行计划前进，他都能看到相同的房间颜色序列。

【样例输入】

11

N 3 5 2

Z 4 5 6

N 7 11 9

N 8 11 10

C 11 9 9

Z 11 9 10

C 11 11 11

C 11 11 11

Z 11 11 11

Z 11 11 11

【样例输出】

8

【提示】

样例如图：

【来源】

POI 2000 The labyrinth of wells