Your task is to maintain a colorful tree and process queries. At the beginning, there is only one vertex numbered 111 with color CCC on the tree. Then there are qqq operations of two types comi
Your task is to maintain a colorful tree and process queries. At the beginning, there is only one vertex numbered 111 with color CCC on the tree. Then there are qqq operations of two types coming in order: 000 xxx ccc ddd: Add a new vertex indexed (n+1)(n+1)(n+1) with color ccc to the tree, where nnn is the current number of existing vertices. An edge connecting vertex xxx and (n+1)(n+1)(n+1) with length ddd will also be added to the tree. 111 xxx ccc: Change the color of vertex xxx to ccc. After each operation, you should find a pair of vertices uuu and vvv (1≤u,v≤n1 le u, v le n1≤u,v≤n) withdifferentcolors in the current tree so that the distance between uuu and vvv is as large as possible. The distance between two vertices uuu and vvv is the length of the shortest path from uuu to vvv on the tree.
