Новый год прошёл, но Resha решил не убирать ёлку, а немного переукрасить её. К нему пришли его друзья Kerim и Gural, чтобы помочь переукрасить ёлку.
Ёлка представляет собой обычное неориентированное дерево из n вершин с корнем в вершине 1.
Вам требуется обрабатывать запросы двух типов:
- Перекрасить все вершины из поддерева вершины v в цвет c.
- Найти количество различных цветов в поддереве вершины v.
Выходные данные
Для каждого запроса второго типа выведите одно целое число a — количество различных цветов в поддереве вершины, заданной в запросе.
Числа нужно выводить в отдельных строках, в порядке появления запросов во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
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
|