Everything changed. At that terrible moment. We knew that home was a tree with
nodes, and carrots were food.
The Land of the Carrot Trees was once a peaceful land, with cities connected with
roads. This all changed one day, when Mimi the carrot-loving cat invaded, and forced the Carrot King into exile!
The Carrot King is constantly on the run. Every day, for the next days, one of two types of events happens:
- His spies tell him that city
has either become a safe haven where he can hide, or if it was safe, that it has been completely overrun. Initially, no city is safe.
- He asks how safe it is to travel from city
to city
. This value is equal to the number of distinct safe cities
such that
is either on the path from
to
, or there exists a city
such that
is on the path from
to
, and there exists an edge between
and
.
As the royal adviser, it is up to you to implement a program that answers the king's queries. Can you save the king?
Constraints
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
Input Specification
The first line of input contains space-separated integers
and
.
The next lines each contain
space-separated integers
and
, indicating there is an edge from
to
.
The next lines first contain an integer
, indicating the type of the event:
- If
, then a single integer
follows.
- If
, then
integers
and
follow.
Output Specification
For each type 2 event, output the answer on a new line.
Sample Input
6 5
1 2
1 3
2 4
4 6
2 5
1 4
2 2 3
2 4 2
1 4
2 5 3
Sample Output
1
1
0
Comments