Девочка очень любит задачи про деревья. Вот одна из них.
Дерево — это неориентированный связный граф без циклов. Степень вершины x в дереве — это количество вершин y дерева таких, что каждая из них связана с вершиной x каким-то ребром дерева.
Рассмотрим дерево, состоящее из n вершин. Будем считать, что вершины этого дерева пронумерованы от 1 до n. Рассматриваемое дерево обладает следующим свойством: каждая вершина, кроме вершины с номером 1, имеет степень не более 2.
Изначально в каждой вершине дерева записано число 0. Ваша задача — быстро выполнять запросы двух типов:
В первой строке заданы числа n (2 ≤ n ≤ 105) и q (1 ≤ q ≤ 105) — количество вершин дерева и количество запросов, соответственно.
Каждая из следующих n - 1 строк содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), которые обозначают, что существует ребро между вершинами с номерами ui и vi. Описание каждого ребра встречается во входных данных ровно один раз. Гарантируется, что заданный граф — дерево, обладающее свойством, которое описано в условии.
Следующие q строк описывают запросы.
Числа в строках разделяются одиночными пробелами.
Для каждого запроса на вывод значения, записанного в вершине, выведите целое число — ответ на запрос.
3 6 1 2 1 3 0 3 1 2 0 2 3 1 0 1 5 2 1 1 1 2 1 3
9 9 6
6 11 1 2 2 5 5 4 1 6 1 3 0 3 1 3 0 3 4 5 0 2 1 4 0 1 5 5 0 4 6 2 1 1 1 2 1 3 1 4 1 5 1 6
11 17 11 16 17 11
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач