Problem E
Enjoying Elderberries

One day, a flock of hungry birds find a huge tree of elderberries. They want to eat all berries of this tree. These birds quickly alight on some leaves of the tree and eat all berries at where they stand. Now they are thinking of who will eat other berries …

Since the flock has some giant birds and some tiny birds, and they observe that the tree has some big branches and some small branches, fairly distributing these berries among all birds turns out to be a tough problem.

Formally, the tree of elderberries can be presented as a tree with the following properties:

• The tree has $n$ vertices numbered from $1$ to $n$. The root of the tree is vertex $1$.

• Each non-leaf vertex (vertex having at least one child) is called a branch. A branch is classified as either big or small. The root is always a big branch.

• On each leaf of the tree, there is either one giant bird, one tiny bird or one elderberry.

The process of determining which bird eats which berry is as below:

• First, every bird and every berry has a label. A label is a non-empty string of at most five lowercase English characters.

• Second, every bird has a controlled area. Consider the bird at vertex $v$:

  • If it is a tiny bird, its controlled area is the subtree rooted at vertex $p_ v$, where $p_ v$ is the parent of $v$.

  • If it is a giant bird, its controlled area is the subtree rooted at vertex $b_ v$, where $b_ v$ is the closest vertex to $v$ among all ancestors of $v$ which are big branches.

• Finally, for each berry, the bird who eats it is determined using the following rules:

  • A bird can only eat berries having the same label with it.

  • A bird can only eat berries inside its controlled area.

  • If there is more than one bird satisfying the two above conditions, only one bird with smallest controlled area eats it.

All birds also set some rules for labeling birds and berries:

• A bird or a berry can have same label with other birds and berries. However, no groups of eight or more birds have the same label.

• Each berry is inside the controlled area of at least one bird with same label.

• No two birds with same label have the same controlled area.

• From all of the above, it can be proven that the bird eating every berry can be uniquely determined.

Sadly, tiny birds think that these rules give advantages to giant birds over them. They claim that, by the rules of setting controlled areas, giant birds usually control larger areas, which means having more berries. (Although their thought is not always true.) They want their controlled areas to be determined using the rules of giant birds. (In other words, they want all tiny birds become giant birds).

Giant birds accept the tiny birds’ claim. However, they try to change the labels of some birds and berries, so that if we assume all tiny birds become giant, the new set of labels still satisfy all the above conditions. Moreover, after changing labels, no berries have changed owner (i.e, every berry is still eaten by the same bird).

They want to change as few labels as possible. Please help them!

Input

The first line contains one integer $n$ $(3 \leq n \leq 150\, 000)$ — the number of vertices in the elderberry tree. The $i$-th of the next $n$ lines describes the $i$-th vertex in either of the following formats:

• ‘$p_ i$ $t_ i$’, where $t_ i$ is either ‘B’ or ‘S’: meaning that $i$ is a branch. $t_ i = B$ and $t_ i = S$ mean that $i$ is a big or small branch, respectively.

• ‘$p_ i$ $T_ i$ $L$’, where $T_ i$ is either ‘G’, ‘T’ or ‘E’ and $L$ is a non-empty string of at most five English characters: meaning that $i$ is a leaf. $t_ i = G, \, t_ i = T$ and $t_ i = E$ mean that in vertex $i$ there is either a giant bird, a tiny bird or an elderberry. $L$ is the label of this bird or berry.

In both formats, $p_ i$ satisfies $1 \leq p_ i < i$ and denotes the parent of vertex $i$. We assume that $p_1 = 0$.

It is guaranteed that the input describes a valid tree, there is at least one bird and one berry, and all labels satisfy the rules presented above. Remember that no eight birds have the same label.

Output

• The first line contains an integer $k$ — the minimum number of labels need changing.

• Each of the next $k$ lines contains an integer $x$ $(1 \leq x \leq n)$ and a label $S$ — meaning that the label of the bird or berry at vertex $x$ is assigned to $S$. $x$ should be a leaf of the tree. $S$ should be a non-empty string of at most five lowercase English characters.

If there are multiple optimal solutions, you can output any one of them.

Explanation for examples

Below are figures depicting these three examples. Red vertices are big branches, green vertices are small branches, violet vertices have giant birds, yellow vertices have tiny birds and white vertices have berries.

• In the first example:

  • Initially:

    • There are $3$ birds with label ‘a’ at vertices $6$, $7$ and $13$. Their controlled areas are the subtrees rooted at vertices $2$, $5$ and $1$, respectively.

    • There is $1$ bird with label ‘b’ at vertex $12$. Its controlled area is the subtree rooted at vertex $1$.

    • There are $3$ elderberries with label ‘a’ at vertices $3$, $8$ and $11$. They are eaten by the birds at vertices $6$, $7$ and $13$, respectively.

    • There are $2$ elderberries with label ‘b’ at vertices $4$ and $9$. They are both eaten by the bird at vertex $12$.

  • If all tiny birds become giant birds, both the controlled area of the birds at vertices $6$ and $7$ become the subtree rooted at vertex $2$, violating the rules (No two birds with same label having same controlled area). Hence, at least one bird’s label needs changing. We can change the label of the bird at vertex $6$ to ‘c’. As the bird at vertex $6$ eats the berry at vertex $3$, we need to change the label of the bird at vertex $3$ as well. The solution in which the bird/berry at vertices $7$ and $8$ get changed is also accepted.

• In the second example:

  • Initially:

    • The controlled areas of the birds at vertices $3$ and $6$ are subtrees rooted at vertices $1$ and $5$, respectively.

    • The bird at vertex $3$ eats the berry at vertex $4$.

  • If all tiny birds become giant birds, their controlled areas are subtrees rooted at vertices $1$ and $2$, respectively. As a result, the bird at vertex $6$ eats the berry at vertex $4$, which is invalid, (The owner of every berry must not change). Hence the label of the bird at vertex $6$ must be changed.

• In the third example, no changes are necessary.

13
0 B
1 B
2 E a
2 E b
2 S
5 G a
5 T a
5 E a
5 E b
1 S
10 E a
10 G b
1 T a

2
3 c
6 c

6
0 B
1 B
1 T a
2 E a
2 S
5 T a

1
6 b

6
0 B
1 G y
1 E y
1 E z
1 T z
1 E z

0