A Special Tree 2

You are given a tree with $N$ nodes (numbered $1$ through $N$). The distance $d(p,q)$ between two nodes $p$ and $q$ of the tree is the number of edges on the unique path between them. There will be $Q$ events each of which can be of the following three types: - '1 u': A certain node $u$ becomes a special node. It is guaranteed that $u$ was not special before this event. - '2 u': A certain node