C. Control Areas
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ is controlled by mafia $$$m_i$$$. Vertex $$$v$$$ is inside the control area of the $$$i$$$-th mafia iff $$$v$$$ is on the shortest path between any two vertices $$$a$$$ and $$$b$$$ (possibly $$$a = b$$$) controlled by this mafia. Your task is to process $$$q$$$ events of the following two types:

  1. Vertex $$$v$$$ is now controlled by mafia $$$c$$$.
  2. Print the number of control areas that one is going to cross on the shortest path between vertices $$$v$$$ and $$$u$$$. Each vertex has a set control areas it belongs to and we ask for the size of the union of these sets for vertices on a path.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$). The next line contains $$$n$$$ integers $$$m_i$$$ ($$$1 \leq m_i \leq n$$$). The next $$$n - 1$$$ lines describe the edges of the tree. Each of these lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \leq v, u \leq n$$$) representing an edge between vertices $$$v$$$ and $$$u$$$. The next $$$q$$$ lines describe the events. Each line starts with one integer $$$t$$$ ($$$1 \leq t \leq 2$$$) representing the type of the event. If:

  • $$$t = 1$$$ then two integers $$$v$$$ and $$$c$$$ ($$$1 \leq v, c \leq n$$$) follow;
  • $$$t = 2$$$ then two integers $$$v$$$ and $$$u$$$ ($$$1 \leq v, u \leq n$$$) follow.
Output

Output one line for each event of type $$$2$$$. The $$$i$$$-th of these lines should contain the answer for the $$$i$$$-th such event from the input.

Example
Input
5 4
1 2 3 1 2
1 2
1 3
3 4
1 5
2 2 5
2 1 4
1 1 2
2 2 3
Output
2
3
2