우물의 미궁

바이트산 깊은 곳에는 우물로 이루어진 신비한 미궁이 있다. 미궁의 입구는 산 꼭대기에 있으며, 미궁은 여러 개의 방으로 이루어져 있다. 각 방은 빨강, 초록, 파랑 세 가지 색 가운데 하나로 칠해져 있다. 색이 같은 두 방은 겉모습이 완전히 똑같아 서로 구별할 수 없다.

각 방에는 $1$, $2$, $3$번으로 번호가 매겨진 우물이 세 개 있다. 방과 방 사이를 이동하는 방법은 우물에 뛰어드는 것뿐이다. 위쪽 방에서 우물에 뛰어들면 (반드시 수직은 아니지만) 그 우물의 아래에 있는 방으로 떨어진다. 입구 방에서 다른 모든 방으로 갈 수 있으며, 미궁의 모든 경로는 결국 가장 아래에 있는 용의 소굴로 이어진다. 미궁을 지나는 한 번의 여정은 차례로 방문하는 방에서 고른 우물 번호의 수열로 나타낼 수 있으며, 이 수열을 여정 계획이라고 부른다.

용의 소굴에는 바이트용이 산다. 전설에 따르면 미궁의 전체 지도를 용에게 바치는 사람은 엄청난 보물을 받고, 그러지 못한 사람은 용의 발길질에 산 밖으로 쫓겨난다.

바이제르라는 영웅은 미궁을 여러 번 지나며 자신만의 지도를 그렸다. 바이트용은 지도에 모든 방이 나오기는 하지만 상당수의 방이 한 번보다 많이 나온다고 말했다.

"나도 예전에 비슷한 그림을 그렸지." 바이트용은 바이제르의 어깨를 두드리며 말했다. "그런데 방을 더 적게 지어도 어떤 여정 계획을 따르든 방문객이 보는 방 색의 수열은 똑같다는 것을 곧 알게 되었다. 그래서 조금 궁리한 끝에 지도를 최대한 줄였지."

바이제르의 지도를 표준 입력으로 읽어, 이 미궁에 실제로 존재하는 방의 개수를 세어 표준 출력으로 출력하는 프로그램을 작성하라.

첫째 줄에 방의 개수를 나타내는 정수 $n$ ($2 \le n \le 6000$)이 주어지며, 이 개수에는 용의 소굴도 포함된다. 방에는 $1$번부터 $n$번까지 번호가 매겨져 있고, 번호가 클수록 아래쪽에 있는 방이다. 입구 방은 $1$번, 용의 소굴은 $n$번이다.

이어지는 $n - 1$개의 줄에는 용의 소굴을 제외한 각 방과 그 방에서 아래로 이어지는 우물이 적혀 있다. 각 줄에는 문자 하나, 공백 하나, 그리고 공백 하나로 구분된 정수 세 개가 있다. 문자는 방의 색을 나타내며 (C는 빨강, Z는 초록, N은 파랑), $i$번째 정수 (단, $i = 1, 2, 3$)는 $i$번 우물이 이어지는 방의 번호이다. 모든 우물은 자기 방보다 번호가 큰 방으로 이어진다.

입력으로 주어진 미궁과 동치인 미궁이 가질 수 있는 방의 최소 개수를 한 줄에 정수 하나로 출력한다. 이 개수에는 용의 소굴도 포함된다. 두 미궁이 동치라는 것은, 어떤 여정 계획을 따르더라도 여행자가 두 미궁에서 보는 방 색의 수열이 서로 같다는 뜻이다.