F. Моё прекрасное безумие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево. Будем рассматривать простые пути в этом дереве. Обозначим путь между вершинами $$$a$$$ и $$$b$$$ как $$$(a, b)$$$. $$$d$$$-окрестностью пути назовём множество вершин дерева, находящихся на расстоянии $$$\leq d$$$ от хотя бы одной вершины пути (например, $$$0$$$-окрестность пути — это сам путь). Пусть $$$P$$$ — мультимножество путей этого дерева, изначально пустое. Нужно обрабатывать следующие запросы:

  • $$$1$$$ $$$u$$$ $$$v$$$ — добавить путь $$$(u, v)$$$ в $$$P$$$ ($$$1 \leq u, v \leq n$$$).
  • $$$2$$$ $$$u$$$ $$$v$$$ — удалить путь $$$(u, v)$$$ из $$$P$$$ ($$$1 \leq u, v \leq n$$$). Заметьте, что $$$(u, v)$$$ и $$$(v, u)$$$ — один и тот же путь. Например, если $$$P = \{(1, 2), (1, 2)\}$$$, то после запроса $$$2$$$ $$$2$$$ $$$1$$$, $$$P = \{(1, 2)\}$$$.
  • $$$3$$$ $$$d$$$ — если пересечение всех $$$d$$$-окрестностей путей, находящихся в $$$P$$$, непусто, выведите «Yes», иначе выведите «No» ($$$0 \leq d \leq n - 1$$$).
Входные данные

В первой строке даны два целых числа $$$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$$$ строк содержат запросы в формате, описанном в условии.

Гарантируется, что:

  • при запросе $$$2$$$ $$$u$$$ $$$v$$$, путь $$$(u, v)$$$ (или $$$(v, u)$$$) содержится в $$$P$$$,
  • при запросе $$$3$$$ $$$d$$$, $$$P \neq \varnothing$$$,
  • есть хотя бы один запрос третьего типа.
Выходные данные

Выведите ответ на каждый запрос третьего типа в отдельной строке.

Примеры
Входные данные
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