Задано корневое дерево, состоящее из n вершин. Каждая вершина дерева имеет определенный цвет. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n. Тогда цвет вершины v будем обозначать cv. Корнем дерева является вершина с номером 1.
В задаче вам требуется ответить на m запросов. Каждый запрос характеризуется двумя целыми числами vj, kj. Ответ на запрос vj, kj — это количество таких цветов вершин x, что в поддереве вершины vj содержится как минимум kj вершин цвета x.
Определение корневого дерева можно прочитать по ссылке: http://ru.wikipedia.org/wiki/Дерево_(теория_графов).
Выходные данные
Выведите m целых чисел — ответы на запросы в порядке появления запросов во входных данных.
Примечание
Поддерево вершины v в корневом дереве с корнем r — это множество вершин дерева {u : dist(r, v) + dist(v, u) = dist(r, u)}. Где dist(x, y) — это длина кратчайшего по количеству ребер пути между вершинами x и y.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3
|
2
2
1
0
1
|
|
2
|
4 1
1 2 3 4
1 2
2 3
3 4
1 1
|
4
|