5406: Growing Tree

There is a growing tree, which has only one node on Day 0 . This node is the root of the tree, numbered 1 and colored c .

On each of the following m days, one of the two types of events below will happen, each of which is described by three integers  t, u, c :

1 u c, which means node u grows a new leaf n + 1 colored c. Or formally, a new node numbered n + 1 and colored c is linked to node u, where n is the number of nodes of the tree at the end of the previous day.

2 u c, which means you want to count the number of nodes colored c in the subtree rooted at node u .

For each type-2 event, output the answer. Please note that the input is encoded.

The first line of the input contains an integer T (1≤T≤105), representing the number of test cases.

The first line of each test case contains two integers , representing the color of node 11 and the number of events.

It is guaranteed that the sum of m over all test cases does not exceed 5*10e5

For each type-2 event, output the answer in a single line.

2
1 3
1 1 2
1 1 1
2 1 1
1 7
2 1 2
1 1 2
2 1 1
0 3 0
0 0 3
3 2 0
3 0 3

2
0
1
1
2

Here is the decoded input of the example:
2
1 3
1 1 2
1 1 1
2 1 1
1 7
2 1 2
1 1 2
2 1 1
1 2 1
1 1 2
2 3 1
2 1 2