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