Вам дано дерево. Будем рассматривать простые пути в этом дереве. Обозначим путь между вершинами \(a\) и \(b\) как \((a, b)\). \(d\)-окрестностью пути назовём множество вершин дерева, находящихся на расстоянии \(\leq d\) от хотя бы одной вершины пути (например, \(0\)-окрестность пути — это сам путь). Пусть \(P\) — мультимножество путей этого дерева, изначально пустое. Нужно обрабатывать следующие запросы:
В первой строке даны два целых числа \(n\) и \(q\) — число вершин в дереве и число запросов, которые нужно обработать, соответственно (\(1 \leq n \leq 2 \cdot 10^5\), \(2 \leq q \leq 2 \cdot 10^5\)).
В следующих \(n - 1\) строках дано описание рёбер дерева. Каждая строка содержит два целых числа \(x_i\) и \(y_i\) — номера вершин, соединенных \(i\)-м ребром (\(1 \le x_i, y_i \le n\)).
Следующие \(q\) строк содержат запросы в формате, описанном в условии.
Гарантируется, что:
Выведите ответ на каждый запрос третьего типа в отдельной строке.
1 4 1 1 1 1 1 1 2 1 1 3 0
Yes
5 3 1 2 1 3 3 4 4 5 1 1 2 1 5 5 3 1
No
10 6 1 2 2 3 3 4 4 7 7 10 2 5 5 6 6 8 8 9 1 9 9 1 9 8 1 8 5 3 0 3 1 3 2
No Yes Yes
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач