Description:

Coco has a tree, whose nodes are conveniently labeled by 1,2,…,n, which has n-1 edge，each edge has a weight. An existing set S is initially empty.

Now there are two kinds of operation:

1 x： If the node x is not in the set S, add node x to the set S

2 x： If the node x is in the set S,delete node x from the set S

Now there is a annoying problem: In order to select a set of edges from tree after each operation which makes any two nodes in set S connected. What is the minimum of the sum of the selected edges’ weight ?

Input:

one integer number T is described in the first line represents the group number of testcases.( T<=10 )

For each test:

The first line has 2 integer number n,q(0<n,q<=100000) describe the number of nodes and the number of operations.

The following n-1 lines each line has 3 integer number u,v,w describe that between node u and node v has an edge weight w.(1<=u,v<=n,1<=w<=100)

The following q lines each line has 2 integer number x,y describe one operation.（x=1 or 2,1<=y<=n）

Output:

Each testcase outputs a line of "Case #x:" , x starts from 1.

The next q line represents the answer to each operation.

Sample Input:

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

Sample Output:

Case #1: 0 6 8 8 4

Source:

Submit