小雷的冰茶幾

Time Limit: 1000MS Memory Limit: 65536KB

PRoblem Description

小雷有個特殊的癖好，平時喜歡收藏各種稀奇古怪的東西，譬如。。。。,還有。。。。，也包括。。。。。小雷是一個喜歡分享的童鞋，這次小雷又給大家?guī)硪惶咨衿娴臇|西，那就是舉世無雙的冰茶幾！ 顧名思義，這些茶幾被冰凍住了，最主要的是他們是易碎品，畢竟被凍住了。因此小雷要很小心翼翼的移動他們。一些茶幾是凍在一起的，因此一套冰茶幾分為好幾部分，并且如果茶幾A與B凍在一起，B與C凍在一起，那么A與C也就凍在了，即冰凍狀態(tài)有傳遞性，ABC此時會看作一個整體。 為了保證冰茶幾的完整性，小雷每次只能移動一整塊冰茶幾，也就是冰凍在一起的一部分。小雷想知道他需要搬幾次才能全部搬到實驗室，你能幫小雷快速計算出答案么？

Input

多組輸入，先輸入組數(shù)T（1 < = T < = 200）。 對于每組輸入，先輸入一個整數(shù)n（1 < = n < = 100000），k（0 < = k < = 100000），茶幾編號1~n。 之后k行，每行兩數(shù)x，y（1 < = x，y < = n），表示第x個茶幾和第y個茶幾冰凍在一起。

Output

對于每組輸入，先輸出”Case z: ”（不帶引號）表示組數(shù)，再輸出一個整數(shù)，表示小雷需要搬動的次數(shù)。

Example Input

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

Example Output

Case 1: 2 Case 2: 3 Case 3: 3

Hint

本題考察并查集，參考http://www.cnblogs.com/Yan-C/p/3943940.html

Submit