Trie

题目描述

---

输入格式

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 ≤ 105).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 ≤ 105), 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^5.

---

输出格式

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

---

样例输入

1
6
1 a
1 b
1 c
3 a
3 b
5
1 2 3 4
2 2 5 6
1 2 2 3
2 2 4 5
2 1 6

---

样例输出

2
3
4

---

提示

---

题目来源

2014 Asia AnShan Regional Contest