Subtree Complement Verification

You are given a tree with n nodes (numbered from 1 to n) and q operations. The tree is rooted at node 1. Initially, you have an empty set S. You need to process q operations on the tree. The operations are of three types:

1. 1 x: Insert node x into the set S.
2. 2: Undo the most recent insert operation (i.e. remove the node that was last inserted into S). It is guaranteed that there is at least one insert before this operation.
3. 3 i: Check whether the current set S is exactly equal to the subtree complement of node i. The subtree complement for a node i is defined as the set of all nodes in the tree T excluding those that are in the subtree of i (including i itself). Here, the subtree of node i is defined by the DFS order (starting from node 1): it consists of all nodes j such that \[ \mathtt{tin}[i] \le \mathtt{tin}[j] \le \mathtt{tout}[i] \] where \(\mathtt{tin}[i]\) and \(\mathtt{tout}[i]\) are the entry and exit times of node i during the DFS traversal.

For each operation of type 3, output YES if S exactly matches the subtree complement of node i; otherwise, output NO.

inputFormat

The first line contains two integers n and q, representing the number of nodes in the tree and the number of operations, respectively.

The next n - 1 lines each contain two integers u and v, representing an edge between nodes u and v.

The following q lines each describe an operation in one of the following formats:

• 1 x — insert operation
• 2 — undo operation
• 3 i — validation (check) operation

outputFormat

For each operation of type 3, output a single line containing either YES or NO depending on whether the current set S equals the subtree complement of node i.

sample

5 7
1 2
1 3
3 4
3 5
1 2
1 4
3 3
2
1 1
3 3
2
3 1

NO
YES
YES