1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int fa[10005];
 5 int vis[10005];
 6 int sig[10005];
 7 int find(int x) {
 8     if(fa[x] == x) {
 9         return x;
10     } else {
11         return fa[x] = find(fa[x]);
12     }
13 }
14 void merge(int x, int y) {
15     int fx = find(x);
16     int fy = find(y);
17     if(fx != fy) {
18         fa[fx] = fy;
19         if(sig[fx]) {
20             sig[fy] = 1;
21         }
22     } else {
23         sig[fx] = 1;
24     }
25 }
26 int main() {
27     int t;
28     cin >> t;
29     for(int i = 1; i <= t; i++) {
30         int n, m;
31         cin >> n >> m;
32         for(int j = 0; j <= n; j++) {
33             fa[j] = j;
34             vis[j] = 0;
35             sig[j] = 0;
36         }
37         int x, y;
38         for(int j = 0; j < m; j++) {
39             cin >> x >> y;
40             vis[x] = 1;
41             vis[y] = 1;
42             merge(x, y); 
43         }
44         int cnt = 0;
45         int huan = 0;
46         for(int j = 1; j <= n; j++) {
47             if(j == fa[j] && vis[j]) {
48                 cnt++;
49                 if(sig[j] == 1) {
50                     huan++;
51                 }
52             }
53         }
54         printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n\n", i, cnt, huan);
55     }
56 
57     return 0;
58 }