Tree

A tree has $N$ nodes numbered 0 to $N-1$. Node 0 is the root, and at the start every other node is a child of node 0. Every edge starts with color 0.

Three operations apply to the tree. They change the shape of the tree or paint its edges.

1. paint(a, b, c): find the shortest path between node a and node b, then paint every edge on that path with color c.
2. move(a, b): change the parent of node a to node b. Node b is never inside the subtree rooted at node a. If p is the parent of node a before the change, the new edge (a, b) keeps the color of the original edge (a, p).
3. count(a, b): find the shortest path between node a and node b, then print how many distinct colors appear on the edges of that path.

A color c is written as an integer.

Consider an initial tree with 6 nodes and the operations move(1,3), move(5,3), paint(5,4,8), move(3,4), paint(0,3,7), count(2,5) applied in that order. Figure 1 is the initial shape. Figures 2 to 4 show, in order, how the shape of the tree and the edge colors change after each operation.

Figure 1. The initial shape

Figure 2. Left: after move(1,3). Right: after move(5,3)

Figure 3. After paint(5,4,8)

Figure 4. Left: after move(3,4). Right: after paint(0,3,7)

The last operation count(2,5) prints 3. As the right half of Figure 4 shows, the edges on the shortest path between node 2 and node 5 carry the colors $\{0, 7, 8\}$, which is three distinct colors.

Given the operations in order, write a program that carries out each one efficiently.

The first line contains the number of nodes $N$ ($1 \le N \le 10^5$) and the number of operations $K$ ($1 \le K \le 3 \times 10^5$). Each of the next $K$ lines holds one operation. The first integer on a line is $r$ ($1 \le r \le 3$), the type of the operation.

• If $r = 1$ the operation is paint, and three more integers follow on the same line: $a$, $b$ ($0 \le a, b \le N-1$) and $c$ ($0 \le c \le 10^9$). Here $a$ and $b$ are node numbers and $c$ is a color number.
• If $r = 2$ the operation is move, and two more integers follow on the same line: $a$ ($1 \le a \le N-1$) and $b$ ($0 \le b \le N-1$). Both are node numbers.
• If $r = 3$ the operation is count, and two more integers follow on the same line: $a$ and $b$ ($0 \le a, b \le N-1$). Both are node numbers.

In the initial tree of $N$ nodes, node 0 is the root, every other node has node 0 as its parent, and every edge has color 0.

For a paint or a count operation, the shortest path between node a and node b always has length at most 1,000.

For each count operation in the input, print its result on its own line, in the order the operations are given. If a and b are equal, the path has no edges, so print 0.