5081：Trie

Little Bob studied Trie in Data Structure class. He learned that Trie is a rooted tree to store some strings. There is a character on each edge of a Trie. (In this problem, the valid characters are lowercase Latin letters.)

Bob draws a Trie with n nodes, and the nodes are numbered with integers from 1 to n. The number of the root node is always 1.

He uses S_i to denote the string concatenated with characters on the path from the root to node i. It can be seen that S1 is the empty string. Furthermore, for a set P {1, 2, . . . , n}, S_P = {S_i | i P}.

Bob defines a kind of trait on this Trie. The trait can be described with a set P {1, 2, . . . , n}. We say a string a has this trait, if and only if there exists a string b S_P such that a ends with b. Here string a ends with string b means the last |b| characters of a is exactly b. (Note that every string ends with the empty string).

Bob also defines a mapping f on P {1, 2, ..., n}, and f (P) is also a subset of {1, 2, . . . , n}. i f (P) if and only if there exists j P such that S_j ends with S_i.

Initially, there is no traits been defined. Bob will add traits whenever he wants. Let D_i denote the number of traits that S_i has until now. Note that D_i may change when a new trait is added.

Besides adding new traits, Bob may also ask you something about his Trie. In each query, Bob will give you a set P {1, 2, . . . , n}, and you need to compute . Are you willing to do this for Bob?

The first line contains an integer T (T ≤ 5), denoting the number of the test cases.

For each test case, the first line contains an integer n(1 ≤ n ≤ 10⁵).

From the second to the n-th line, this n - 1 lines describe Bob' s Trie. The i-th line contains an integer u(u < i), and a lowercase letter c, which means that the father of node i is node u and the character on that edge is c. We ensure that for each node i, letters on edges connecting i and its children are all different.

The next line contains an integer m(m ≤ 10⁵), which means there are m operations.

The next m lines describe all operations. In each line, the first integer indicates the type of this operation. 1 means Bob will add a new trait and 2 means Bob is asking you a question. The second integer k is the size of set P , and the next k integers are the elements of P. We ensure that these k integers are different, and they are all between 1 and n. The total size of the m sets will not be larger than 5·10⁵.

For each test case, output the answer for each query operation, one answer in a line.