Last year, our largest rainforest Amazon suffered the worst wildfire of the decade. The wildfire caused devastation and burned many trees. We need to get prepared as this kind of wildfire can be back at any time. You are a great programmer and you are working with the firefighters to make a computer program.
The firefighters have located some important points at Amazon where local people live. The points are numbered from $\textbf 1$ to $\textbf N$. People travel from one point to another through paths. A path consists of one or more roads. A road connects a point with another point. Those roads are surrounded by many tall trees of Amazon. If there is a wildfire in the forest near any road, people avoid it. Sometimes, it can be impossible to travel from one point to another. The reason is that there is only one path between two points. If the road catches fire, people can not go through it. The firefighters need the updated information about the status of the path between the points.
You program will be given the map of the points. When a wildfire catches Amazon, your program will assist the firefighters by taking the inputs and sending the relevant information as output. Your program will assist them from a server and the firefighters will access it with their device.
First line of the input will contain an integer number $\textbf N$ $(2 \leq N \leq 10^{5})$.
Then there will be $\textbf N-1$ lines. Each of them will contain two inters $\textbf U$ and $\textbf V$ seperated by space. It means that there is a direct road between $\textbf U$ and $\textbf V$ $(1\leq U,V\leq N $ and $U \neq V)$. Note that till now all the roads have caught fire.
After that, there will be an integer $\textbf Q$ $(1 \leq Q \leq 4\times 10^{5})$ which denotes the number of inputs coming from the firefighters.
The next $\textbf Q$ lines will contain one of the three types of inputs. Each of the inputs will start with a string which will indicate the type of the input. So, the queries will be like below:
$update$ $U$ $V$:
This input will come from firefighters which means they have estinguished fire near the road between U and V now. It will update the information of the road in the program's database. The output of this query will be an integer $C$ which denotes the size of the $Group$ which contains the points $U$ and $V$ where $(1\leq U,V\leq N $ and $U \neq V)$. $Group$ means a set of points in the forest that there is a path between any pair of them without fire. Size of the $Group$ means the total number of points in that group.
$query$ $U$ $V$:
This input will come from firefighters and it will output a string $\text{YES}$ or $\text{NO}$ dependending on the current status of the path between $\textbf U$ and $\textbf V$ where $(1\leq U,V\leq N $ and $U \neq V)$. If there is a path between $\textbf U$ and $\textbf V$ without fire then your program will say YES, otherwise NO.
$back$ $T$:
This input will inform the program that all the updates that changed the roads' statuses and executed after the T-th input will be discarded. Output of this query will be an integer $\textbf M$ . $\textbf M$ denotes the number of groups of points. Group means a set of points in the forest that there is a path between any pair of them without fire. $i \leq T_j < j$ where $i \leq j$ and the $i^{th}$,$j^{th}$ query contains a query of type $back$ $T$.
For each type of input, print the desired result described in the input section in a line.
| Input | Output |
|---|---|
5 1 2 2 3 3 4 4 5 8 update 4 5 update 3 4 update 2 3 query 2 3 back 2 query 2 3 query 3 4 query 4 5 | 2 3 4 YES 3 NO YES YES |