F. The Ropeways
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

On the mysterious planet Taeladus, each of your bases is linked by several ropeways, but due to the scarcity of resources at the time you used the minimum number of $$$n-1$$$ ropeways to connect your $$$n$$$ bases.

Unfortunately, some of the ropeways have already broken due to damage from the Angel. What's more unfortunate is that the direction of the ropeway station has already been determined, so you and your team $$$\textbf{can only repair the ropeways that once existed}$$$.

But luckily, some staff from Rhodes Island helped you fix part of the ropeways.

Right now you only have enough resources on hand to $$$\textbf{temporarily repair a ropeway}$$$.We call a base station that can be reached with only the resources at hand $$$\textbf{quickly reachable}$$$.

Now you want to know how many bases are $$$\textbf{quickly reachable}$$$ from the asked base.We are sure as the Endministrator you can figure it out pretty quickly.

Formally, given a tree with edge lengths $$$0$$$ or $$$1$$$ and edge lengths that may be modified multiple times. You will be asked several times how many nodes whose distance is less than or equal to $$$1$$$ from the query node (count itself).

Input

The first row has two numbers $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$), $$$m$$$ ($$$1 \leq m \leq 2 \times 10^5$$$), where $$$n$$$ represents the number of bases and $$$m$$$ represents the number of events.

Next, $$$n-1$$$ rows, each with three numbers $$$a$$$,$$$b$$$ ($$$1 \leq a,b \leq n$$$), and $$$c$$$ ($$$c \in \{0,1\}$$$) indicate whether a ropeway links base $$$a$$$ to base $$$b$$$ and whether it is broken ($$$1$$$ means broken, $$$0$$$ means link).

Next, $$$m$$$ rows, two numbers in each row, $$$op$$$ ($$$op \in \{1,2\}$$$) and $$$x$$$. When $$$op$$$ is $$$1$$$, it means to modify the state of the $$$x$$$-th ropeway ($$$1$$$ changes to $$$0$$$, $$$0$$$ changes to $$$1$$$) (in this case $$$1 \leq x \leq n - 1$$$). When $$$op$$$ is $$$2$$$, it means to ask how many bases can be reached from base $$$x$$$ if only one ropeway can be repaired (in this case $$$1 \leq x \leq n$$$).

Output

For each event with an $$$op$$$ of $$$2$$$, output how many bases can be reached from base $$$x$$$ if only one ropeway can be repaired.

Example
Input
6 4
1 2 1
2 3 0
3 4 0
3 5 0
1 6 0
2 3
1 2
2 3
2 2
Output
6
4
6