+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- + RRRRIIIIIING….. RRRIIIIIINNNGG…. + Hello? Yes. Yes it's me. Okay, be there ASAP. Guys? We got a situation. Minutes after the telephone at “The Overweight Police” (also known as “Police-e fat ha”) headquarters rang, the officers moved out in helicopters to take care of the situation. It's a robbery. TIGH (TIGH Infamous Group of Hackers) are disappointed in their laptops this time and have set their green-text-on-a-black-background terminals aside to attack the KFC (KFC Federal Club) building in person! $n-1$ rooms and a roof combine for $n$ occupiable places in KFC. The rooms in KFC like the ones in any other ordinary building, are uniquely numbered from $2$ to $n$. Roof is assigned the number $1$. There are $n-1$ staircases in the building which are the only means to move from one room (or roof) to another. Each staircase connects $2$ different rooms(or a room and the roof). It is known that there exists a unique way to go from the roof to any other room in the building if you only move down the staircases (Which means the setting of the rooms and the staircases among them forms a tree). The victim is Gigi who He has been to a party last week. Just like everybody else, Gigi took countless pictures at they party with his sisters, mothers[citation needed], cousins, aunts and his brothers' wives. He's such a kind person that he took pictures with every single one of her $84$ daughters too (Unfortunately one of her daughters was not present at the party). As you know hackers continuously strive and plan to steal random family pictures from random people (not so random in this case. Coincidence? I guess not). TIGH is no exception. But wait! There's more! As you know “police-e fatha looks after everything”. They're not gonna let TIGH escape without a fight. In $m$ seconds, $m$ events happen in order, each of which fits in exactly one of the following two categories: + A member of TIGH steals the photos in the room number $x$. + An overweight police jumps in the room number $y$ from the helicopter. Hence the name, police-e fatha don't like physical activities very much. Also they are pretty optimistic, so every time an overweight police jumps off from the helicopter into a room, she thinks about what is the maximum number of TIGH members that she could catch if she only used the staircases downwards considering she is “lucky”. An overweight police can catch a TIGH member if and only if they are in the same room at some moment. The members of TIGH are as optimistic as fatha. When they steal some photos they would try to escape through the roof (using the command “$sudo teleport” which only works in the rooftops). Since TIGH members are not out of their minds, they will only use staircases upwards. they think to themselves what is the minimum number of fat polices that they have to escape from to reach the rooftop considering they are “lucky”. A TIGH member has to escape from a fat police if and only if they are in the same room at some moment. TIGH members are aware of the fact that the cops only move downwards, and the cops know that the hackers will only move towards the roof. Please note that nobody actually moves from her initial position. They only “think” about what would happen if everybody suddenly had the ability to move (with the conditions specified above). The term “lucky” in the above statements means that everyone thinks about her own best-case scenario. For example a lucky situation for a cop would be just waiting in his initial node, and catch every TIGH member that tries to pass him. You can prove that this strategy yields the maximum number of hackers that can be caught by the cop. For a better understanding take a look at the samples. # ورودی The first line of the input will consist of two numbers $n$ and $m$, $$0 \lt n \lt 10^5, \quad \quad 0 \lt m \lt 10^5$$ then follow $n-1$ lines each of which describing a staircase in the building “from” room number $x_i$ “downward” to room number $y_i$. The next $m$ lines are of the form “$t_i\,x_i$” where $1\leq t_i \leq 2$. $t_i = 1$ means that an overweight police is placed in the room number $x_i$ and $t_i = 2$ means that a TIGH member steals photos from the room number $x_i$. # خروجی Output $m$ integers in different lines, $i$th of them is the answer to the question that the person in the $i$th event asks herself. # مثال‌ها ## ورودی نمونه ۱ ``` 8 10 1 2 2 3 3 4 1 5 5 6 6 7 5 8 1 1 1 2 2 2 2 3 1 3 2 4 1 1 2 5 2 7 1 5 ``` ## خروجی نمونه ۱ ``` 0 0 1 1 1 2 3 0 0 2 ``` 1. No tigh member at all, therefore the answer is 0. 2. Still no tigh member. 3. A hacker and a cop are at room number 2, therefore the the hacker definitely has to escape him. There is also a cop on the roof too but if the hacker is “lucky”, she can wait for that cop to take the staircase from 1 downward to 4 (Note that the cop can not come back up the staircases). So in the best case scenario she will only encounter the cop at room number 2. 4. no matter how lucky the hacker is, she has to get passed the second cop, because she will only move upwards and the cop will only move downwards. Again in the best-case scenario she can avoid the first cop. 5. the cop can catch the hacker which occupies the same room with him. 6. Like the above cases, the hacker has to pass along the second and third cops no matter how well things go. Again she can avoid the first (in the input) cop. 7. If the cop is lucky, she can wait at where she is placed (roof) for all the hackers in the lower levels. Therefore in the best-case scenario she can catch them all. 8. The hacker can avoid both of the cops at #1. (wait for both of them to go towards room #2). 9. Same as above. 10. This cop can catch the hacker which had been previously placed in room number 5. Also in the best-case scenario for him, he will wait until the hacker in the room #7 comes up the stairs and he will arrest him.

حل سؤال در بانک سؤالات