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:
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:
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.
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
2 3 2
| Название |
|---|


