Kyriakos Grizzly is planning a meetup with his $N-1$ grizzly friends! The grizzlies are numbered from $1$ to $N$ (Kyriakos is grizzly $1$), and the $i^{\text{th}}$ grizzly lives in city $i$. Their plan is to meet up in city $1$ where Kyriakos lives. Being smart grizzlies, they will each take the shortest path to city $1$ along the network of roads that connects the cities. As a result, the roads that they will use form a tree with $N-1$ edges. After arriving at city $v$, a grizzly will wait for all other grizzlies that will pass through city $v$, so that they can travel together to the next cities.

Being generous as well as smart, when two grizzlies meet for the first time, they will both buy each other a gift from the city in which they met. By the time that all grizzlies have met in city $1$, they should have each received $N-1$ gifts, one from each of the other grizzlies. A gift from city $i$ has two properties: a price $p_i$ and a quality $q_i$. A grizzly's confusion value will be the number of pairs of gifts that he received such that the first gift is from city $i$ and the second is from city $j$ and $p_i<p_j$ and $q_i>q_j$.

Kyriakos would like you to find the total confusion value among the $N$ grizzlies if they all attended the meetup. However, he also expects one or two grizzlies to cancel on their plans (they will not attend the meetup). Therefore, he will ask you an additional $Q$ questions. There will be two types of questions:

• 1 v If grizzly $v$ decides to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?
• 2 u v If grizzlies $u$ and $v$ decide to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?

Constraints

$2\le N\le 150000$

$0\le Q\le 150000$

$1\le p_i,q_i,u_i,v_i\le N$

All $p_i$ are distinct.

All $q_i$ are distinct.

For all questions, $1\le u\le N$.

For type 2 questions, $1\le v\le N$ and $u\ne v$.

Subtask 1 [20%]

$Q=0$

Subtask 2 [40%]

All questions are of type 1.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers, $N$ and $Q$.

The following $N$ lines will contain two space-separated integers each, $p_i$ and $q_i$.

The following $N-1$ lines will contain two space-separated integers each, $u_i$ and $v_i$, denoting an edge in the tree.

The following $Q$ lines each describe a question.

Output Specification

Output one line containing the total confusion value among all $N$ grizzlies if they all attended the meetup.

Output an additional $Q$ lines containing the answers for each of the questions.

Sample Input 1

5 0
5 5
1 3
4 1
2 4
3 2
2 1
3 2
4 3
5 4

Sample Output 1

6

Sample Input 2

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

Sample Output 2

12
4
4
6
4
6

Sample Input 3

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

Sample Output 3

12
2
2
0
2
2