For a tree with n vertices, each vertex can be either white or black, initially all vertices are white. There are q queries, each falling into one of two forms:
- 1u: All vertices on the path from the root to u will become black.
- 2u: All vertices in the subtree rooted at u will become white.
For each query, determine the number of vertices that change color after the query is executed.
### Input
- The first line consists of two integers n,q.
- The next n−1 lines, each containing two integers u,v, indicating an edge between u and v.
- The next q lines, each representing a query in the specified format.
### Output
- After each query, print the number of vertices that change color.
### Constraints
- 1≤n,q≤105.
- 1≤u,v≤n.
### Sample test
Input
64121334352612231423
Output:
2022