Девочка очень любит задачи про деревья. Вот одна из них.
Дерево — это неориентированный связный граф без циклов. Степень вершины 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
| Codeforces Round 169 (Div. 2) |
|---|
| Закончено |
