2012年12月15日 星期六

11770 - Lighting Away


Ronju 是「Lavish 辦公大樓」總部的夜間守衛,辦公大樓前有一大片草地,因此每天傍晚 Ronju 來值班時,他個工作就是把草地上的燈打開。然而,對於那麼大片的草地以及為數眾多的燈,這件工作就會相當地累人。

因此他設計了一個巧妙的解決方案--他將手動開關換成光敏觸發開關(light-sensitive trigger)。當地附近的商店以非常便宜的價格來賣這些光敏觸發開關,一旦這些開關照到光,他將自動打開燈光,即使附近某些燈被點亮,他也會感應到。自此之後,Ronju 只要手動打開一些燈,這些燈的燈光就會觸發鄰近的感應器,使得更多的燈被點亮,最終整個草地將會被點亮。

現在 Ronju 想知道:他需要手動打開多少個開關呢?

輸入

輸入一開始有一整數 T,代表接下來的測試組數。每組測資一開始有兩個整數 N ($1{\leq}N{\leq}10000$) 和 M ($1{\leq}M{\leq}100000$),N 代表草地上燈的數量。接下來會有 M 行輸入,每行有兩個以空白隔開的正整數 a、b,$1{\leq}a, b{\leq}N$,代表如果燈泡 a 亮了,就會觸發燈泡 b 也讓 b 一起亮 (依據兩燈間的距離、亮度、感應器靈敏度、方向和其他複雜的因素)。最後,每個測試資料後都有一個空白隔開。

輸出

對於每筆輸入測資,輸出一行格式如「Case k: c」,k 代表測試資料的編號,從 1 開始編號;c 代表最小 Ronju 必須手動打開燈光的數量。

範例輸入

2
5 4
1 2
1 3
3 4
5 3

4 4
1 2
1 3
4 2
4 3


範例輸出

Case 1: 2
Case 2: 2


Problemsetter: Samee Zahur
Special Thanks:  Jane Alam Jan