Вам дано дерево. Будем рассматривать простые пути в этом дереве. Обозначим путь между вершинами \(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\)).
Выходные данные
Выведите ответ на каждый запрос третьего типа в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 4
1 1 1
1 1 1
2 1 1
3 0
|
Yes
|
|
2
|
5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1
|
No
|
|
3
|
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
|