2558. [Poi2000]迷宫的墙
#2558. [Poi2000]迷宫的墙
题目描述
神话中的Byte山上有一座迷宫。迷宫的入口坐落在山顶。迷宫由红色、绿色或蓝色的房间组成。两间相同颜色的房间看上去完全一样无法区别。每个房间内有编号为1、2、3的三堵墙，从房间到房间，只有穿过上面房间的一堵墙到下面的房间（不一定垂直地穿过）。从入口处的房间可以到达其它任一房间，所有的通道最终都通向最底层的龙穴。通过迷宫的一次旅行可用一系列在房间内选择要穿过的墙的编号来表示。这样的一个序列，称为一个行程计划。
Byte龙就住在龙穴里。传说，如果谁能画出这个迷宫的地图，并献给龙，谁就将得到一大笔财富；但如果失败了，就会被Byte龙一脚踢下山。
一个叫Bytezar的英雄历尽艰辛终于画出了一份地图，然而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