F. My Beautiful Madness
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree. We will consider simple paths on it. Let's denote path between vertices $$$a$$$ and $$$b$$$ as $$$(a, b)$$$. Let $$$d$$$-neighborhood of a path be a set of vertices of the tree located at a distance $$$\leq d$$$ from at least one vertex of the path (for example, $$$0$$$-neighborhood of a path is a path itself). Let $$$P$$$ be a multiset of the tree paths. Initially, it is empty. You are asked to maintain the following queries:

  • $$$1$$$ $$$u$$$ $$$v$$$ — add path $$$(u, v)$$$ into $$$P$$$ ($$$1 \leq u, v \leq n$$$).
  • $$$2$$$ $$$u$$$ $$$v$$$ — delete path $$$(u, v)$$$ from $$$P$$$ ($$$1 \leq u, v \leq n$$$). Notice that $$$(u, v)$$$ equals to $$$(v, u)$$$. For example, if $$$P = \{(1, 2), (1, 2)\}$$$, than after query $$$2$$$ $$$2$$$ $$$1$$$, $$$P = \{(1, 2)\}$$$.
  • $$$3$$$ $$$d$$$ — if intersection of all $$$d$$$-neighborhoods of paths from $$$P$$$ is not empty output "Yes", otherwise output "No" ($$$0 \leq d \leq n - 1$$$).
Input

The first line contains two integers $$$n$$$ and $$$q$$$ — the number of vertices in the tree and the number of queries, accordingly ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq q \leq 2 \cdot 10^5$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — indices of vertices connected by $$$i$$$-th edge ($$$1 \le x_i, y_i \le n$$$).

The following $$$q$$$ lines contain queries in the format described in the statement.

It's guaranteed that:

  • for a query $$$2$$$ $$$u$$$ $$$v$$$, path $$$(u, v)$$$ (or $$$(v, u)$$$) is present in $$$P$$$,
  • for a query $$$3$$$ $$$d$$$, $$$P \neq \varnothing$$$,
  • there is at least one query of the third type.
Output

For each query of the third type output answer on a new line.

Examples
Input
1 4
1 1 1
1 1 1
2 1 1
3 0
Output
Yes
Input
5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1
Output
No
Input
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
Output
No
Yes
Yes