Inkopolis

Time Limit: 24000/12000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description


Inkopolis is the city in which Inklings live in, it can be regarded as an undirected connected graph with exactly $N$ vertices and $N$ edges between vertices. It is guaranteed that the graph doesn’t contain duplicated edges or self loops. Inklings can splatter a special type of colored ink to decorate the roads they live in. Inklings are capricious so they often change the color of the roads to celebrate the upcoming Splatfest.
The Splatfest lasts for exactly $M$ days, on each day Inklings will splatter ink on exactly one road, the color on this road will be coverd by the new color of the ink. At the end of each day, they wonder how many different colored regions are there in the Inkopolis. A colored region is a set of connected roads with same color, to be clear, two roads are in the same colored region if they have the same color and share a common vertex.

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
For each test case, the first line contains two integers $N$ and $M$, where $N$ is the number of vertexes and roads in Inkopolis, and $M$ is the number of days that Splatfest lasts.
Following $N$ lines describe the roads between the vertexes. Each line contains 3 integers $x$, $y$, $c$, representing there is a road with color $c$ between the $x^{th}$ and the $y^{th}$ vertex.
Next following $M$ lines describe the operations on each day. Each line contains 3 integers $x$, $y$, $c$, representing an operation that Inklings splatter the ink with color $c$ to the road between the $x^{th}$ and the $y^{th}$ vertex, it is guaranteed that there is such a road.
$1 \leq T \leq 100$
$3 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq x, y, c \leq n$
$\sum N, \sum M \leq 10^6$

Output

For each test case, output one line containing “Case #x:” first, where $x$ is the test case number (starting from 1).
The following $M$ lines each consists of an integer which is the number of colored regional in Inkopolis after each day.

Sample Input

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

Sample Output

Case #1: 4 3 3 Case #2: 2 4 2 2

Hint

liuyiding

Source

2017中国大学生程序设计竞赛-总决赛-重现赛(感谢哈工大)

提交代码