E. Новогодняя ёлка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Новый год прошёл, но Resha решил не убирать ёлку, а немного переукрасить её. К нему пришли его друзья Kerim и Gural, чтобы помочь переукрасить ёлку.

Ёлка представляет собой обычное неориентированное дерево из n вершин с корнем в вершине 1.

Вам требуется обрабатывать запросы двух типов:

  1. Перекрасить все вершины из поддерева вершины v в цвет c.
  2. Найти количество различных цветов в поддереве вершины v.
Входные данные

В первой строке находится пара целых чисел n, m (1 ≤ n, m ≤ 4·105) — количество вершин в дереве и количество запросов.

Во второй строке находятся n целых чисел ci (1 ≤ ci ≤ 60) — цвет i-й вершины.

В каждой из следующих n - 1 строк находится пара целых чисел xj, yj (1 ≤ xj, yj ≤ n) — вершины, которые соединяет j-е ребро дерева. Гарантируется, что вам задано корректное неориентированное дерево.

В последних m строках находятся описания запросов. Каждое описание начинается с целого цисла tk (1 ≤ tk ≤ 2) — типа запроса. Для запросов первого типа далее следует пара целых чисел vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — номер вершины дерева в поддереве которой все вершины перекрашиваются в цвет ck. Для запросов второго типа далее следует целое число vk (1 ≤ vk ≤ n) — номер вершины в поддереве которой нужно посчитать количество различных цветов.

Выходные данные

Для каждого запроса второго типа выведите одно целое число a — количество различных цветов в поддереве вершины, заданной в запросе.

Числа нужно выводить в отдельных строках, в порядке появления запросов во входных данных.

Примеры
Входные данные
7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3
Выходные данные
2
3
4
5
1
2
Входные данные
23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
Выходные данные
6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3