NOW I HAVE THE POWER ~ Victor, 2019

Victor, using the money he earned from selling horseshoe crabs, has managed to buy alien technology!

Using this alien technology, he terraforms Canada into a network of cities, numbered connected by exactly highways.
Victor lives in city .

He also hires aliens (numbered ) to guard the cities with.
As alien guards are *expensive*, each city has exactly guard assigned to it.
An alien can be assigned to multiple cities, but can be present in at most one city at a time (thankfully, these aliens don't teleport).

Over the following minutes, one of the following happens:

`1 c k`

: Alien is assigned to guard city , replacing its previous alien guard.`2 u`

: The resistance plans a siege of city and wishes to know the maximum possible number of guards that can come reinforce city .

As the head of intelligence at the resistance, you are tasked with writing a program to calculate these scenarios. A guard is able to reinforce city if and only if lies on the unique path between any one of its assigned cities and city .

*If only Victor hadn't been given the roll of paper of power...*

#### Constraints

For all subtasks:

##### Subtask 1 [10%]

##### Subtask 2 [20%]

The alien guards are never reassigned.

##### Subtask 3 [40%]

##### Subtask 4 [30%]

#### Input Specification

The first line will contain three space-separated integers, , , and .

The second line will contain space-separated integers, , indicating the th alien is assigned to city .

The next lines will each contain a pair of integers, , indicating there is an edge between and .

The next lines will each contain a query.

#### Output Specification

For each expedition, output the maximum possible number of guards that can come reinforce city .

#### Sample Input 1

```
5 5 5
3 4 1 1 2
1 2
1 3
2 4
2 5
2 2
2 1
1 2 1
2 2
2 1
```

#### Sample Output 1

```
3
4
2
3
```

#### Sample Input 2

```
7 5 4
1 2 3 4 3 2 1
1 2
1 3
1 4
4 5
4 6
4 7
2 4
2 1
2 2
2 7
```

#### Sample Output 2

```
4
4
1
1
```

## Comments