Kyriakos Grizzly is planning a meetup with his grizzly friends! The grizzlies are numbered from
to
(Kyriakos is grizzly
), and the
grizzly lives in city
. Their plan is to meet up in city
where Kyriakos lives. Being smart grizzlies, they will each take the shortest path to city
along the network of roads that connects the cities. As a result, the roads that they will use form a tree with
edges. After arriving at city
, a grizzly will wait for all other grizzlies that will pass through city
, 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 , they should have each received
gifts, one from each of the other grizzlies. A gift from city
has two properties: a price
and a quality
. A grizzly's confusion value will be the number of pairs of gifts that he received such that the first gift is from city
and the second is from city
and
and
.
Kyriakos would like you to find the total confusion value among the 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
questions. There will be two types of questions:
1 v
If grizzlydecides to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?
2 u v
If grizzliesand
decide to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?
Constraints
All are distinct.
All are distinct.
For all questions, .
For type 2 questions, and
.
Subtask 1 [20%]
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, and
.
The following lines will contain two space-separated integers each,
and
.
The following lines will contain two space-separated integers each,
and
, denoting an edge in the tree.
The following lines each describe a question.
Output Specification
Output one line containing the total confusion value among all grizzlies if they all attended the meetup.
Output an additional 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
Comments