题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入有若干组数据，每组数据的第一行是一个正整数 N，表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

输出格式

输入中有多少组数据，输出中就有多少行。每行对应一组输入数据的结果。

其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输出格式参照以下输入输出样例。

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

Case 1: 2 4
Case 2: 4 1

500
1 2
1 3
1 66
1 88
1 231
2 15
2 66
2 72
2 118
2 157
3 4
3 5
3 6
3 7
3 9
3 10
3 139
3 189
4 17
4 18
4 105
4 204
4 250
5 28
5 50
5 56
5 83
5 130
6 13
6 76
6 116
6 141
7 8
7 29
7 145
7 242
8 10
8 11
8 12
8 21
8 32
8 215
9 16
9 26
9 72
9 139
9 141
9 164
9 209
9 223
10 14
10 198
11 16
11 20
11 68
11 83
11 86
11 105
11 137
11 209
11 225
12 174
12 210
12 227
13 56
13 67
13 159
14 23
14 39
14 42
14 48
14 61
14 68
14 111
14 189
15 112
15 174
16 35
16 66
16 105
16 115
16 147
16 155
16 169
16 195
16 220
17 19
17 21
17 25
17 41
17 78
17 79
17 92
17 153
17 204
18 24
18 30
18 34
18 53
18 122
18 201
19 22
19 27
19 33
19 40
19 47
20 115
20 178
20 191
20 226
20 231
21 103
21 129
21 170
22 25
22 31
22 55
22 94
22 143
22 202
22 235
23 58
23 121
23 205
24 52
24 61
24 140
25 26
25 28
25 46
25 65
25 106
25 204
25 207
25 232
26 43
26 51
27 91
27 114
28 36
28 62
28 74
28 78
28 112
28 115
28 185
28 191
30 32
30 38
30 45
30 55
30 125
30 133
30 180
30 239
31 34
31 60
31 73
31 157
31 185
32 102
32 107
32 150
32 178
32 201
33 48
33 72
33 155
34 41
34 44
34 63
34 154
35 37
35 45
35 71
35 228
36 49
36 171
36 228
37 80
37 94
37 173
37 227
37 245
38 39
38 59
38 66
38 117
40 64
40 119
41 57
41 76
41 123
41 162
41 165
41 190
42 75
42 132
43 82
43 208
43 227
44 134
44 179
44 194
44 217
46 104
46 138
46 238
47 95
48 135
49 160
49 181
50 101
50 158
50 201
51 138
52 70
52 100
52 116
52 165
52 172
52 196
53 54
53 65
54 60
54 76
54 99
54 108
55 90
55 194
56 97
56 205
56 224
56 241
57 168
58 63
58 69
58 98
59 71
59 113
59 131
59 136
59 141
59 194
59 236
59 240
60 113
61 86
61 123
62 98
62 106
62 147
62 182
62 200
63 69
63 102
63 128
63 244
64 85
64 104
64 140
64 147
64 151
64 224
64 229
66 96
66 133
66 246
67 93
67 158
67 208
68 75
68 77
68 88
68 217
68 237
69 73
69 79
69 81
69 87
69 89
69 130
69 188
69 238
71 205
72 101
72 155
73 105
73 135
73 221
74 116
74 172
74 225
74 231
75 139
75 214
76 84
76 125
76 145
77 81
77 110
77 122
77 139
77 186
77 195
78 102
78 146
78 148
78 203
78 206
79 209
79 250
80 126
80 208
80 228
82 103
82 175
82 227
82 247
83 104
83 114
83 119
83 127
83 142
83 161
86 228
87 119
87 172
88 174
88 192
90 170
91 95
91 146
91 207
92 126
92 176
93 113
93 224
93 241
95 160
96 166
96 222
96 229
96 242
97 106
97 163
98 151
98 173
98 207
99 109
99 148
99 149
100 111
100 246
101 123
101 160
102 231
103 179
104 116
104 117
104 141
105 120
105 200
106 156
106 211
107 124
107 155
108 129
108 168
108 198
108 222
110 146
110 169
110 228
111 130
111 193
112 163
112 218
112 242
113 198
114 145
114 188
115 192
116 177
116 187
116 197
116 216
117 213
118 168
118 191
119 154
119 198
120 231
121 184
122 136
122 172
123 237
126 137
126 144
127 156
127 186
128 181
129 147
129 148
131 178
131 229
132 181
132 182
132 201
132 212
132 218
134 197
135 144
135 150
135 151
137 159
137 166
137 179
137 219
137 242
139 219
141 151
141 195
141 245
142 183
142 248
143 248
144 217
145 161
146 164
146 167
146 188
148 151
148 152
148 168
148 172
149 207
150 160
150 231
151 160
151 172
151 243
155 156
155 181
155 231
155 233
155 244
156 230
157 180
157 191
158 240
159 192
159 206
160 197
160 210
160 230
161 212
162 182
162 223
164 232
167 179
167 184
172 196
174 209
175 202
175 220
176 182
176 217
176 234
179 206
183 214
184 195
184 220
185 205
185 234
188 199
188 201
189 191
189 221
191 229
194 244
195 197
196 222
196 239
196 243
197 211
198 224
202 228
204 243
205 232
205 241
208 222
209 238
209 240
210 215
219 226
222 248
227 243
233 249
240 245
0

Case 1: 22 1

37
1 2
1 4
1 7
1 8
1 18
2 3
3 5
3 6
3 11
3 16
4 12
4 17
4 18
5 7
5 8
5 10
6 9
6 11
6 15
6 16
8 10
8 12
8 13
8 16
9 16
10 11
10 12
10 13
10 16
11 15
11 17
11 18
12 13
12 14
13 14
14 16
17 18
0

Case 1: 2 153

数据范围与约定

N≤500，输入数据保证答案小于 2^64。