396. mine site construction

The coal mining site can be regarded as an undirected graph composed of tunnels connecting coal mining points .

To be on the safe side , It is hoped that when an accident occurs at the construction site, all the workers at the coal mining point can have a way out and escape to the rescue exit .

So the mine owner decided to set up rescue exits at some coal mining sites , So that no matter which coal mining point collapses , Workers at other coal mining sites have a road leading to the rescue exit .

Please write a program , It is used to calculate that at least several rescue exits need to be set , And the total number of setting schemes of different minimum rescue exits .

Input format

The input file has several sets of data , The first row of each set of data is a positive integer N, Indicates the number of tunnels on the construction site .

Next N Each line is two integers separated by spaces S and T, Indicates the coal mining point S And coal mining points T Directly connected by a tunnel .

Be careful , The number of coal mining points for each group of data is 1∼Max, among Max Represents the coal excavation point connected by the tunnel , The number of the largest coal mining point , There may be coal mining points that are not connected by the tunnel .

Enter data to 0 ending .

Output format

Each group of data output results occupy one line .

Among them the first i Line to Case i: Start （ Pay attention to case ,Case And i There's a space between ,i And : No space between ,: There is a space after ）.

Followed by two positive integers separated by spaces , The first positive integer indicates that for the i At least several rescue exits shall be set for group input data , The second positive integer indicates that for the second i The total number of setting schemes for the minimum rescue exits with different group input data .

Input data to ensure that the answer is less than 264, Refer to the following input and output examples for output format .

Data range

1≤N≤500,
1≤Max≤1000

sample input ：

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

sample output ：

Case 1: 2 4
Case 2: 4 1

Ideas ：

/*  Give an undirected graph that is not necessarily connected   Ask at least how many points to set the exit   Make any one of the exits broken , All other points can be connected to some exits   First consider  1  Number of exports >=2  If there is only one exit   If the outlet is broken, there will be no outlet available （ The solitary point judges alone ） 2  Different connected blocks are independent of each other ( Number of final proposals  =  Product of the number of schemes of each connected block )  For a connected block  2.1  No cut point  <=>  No matter which point I delete   The rest of the graph is connected 、 And there are still good exits >=1 <=>  Degrees ==0 <=>  Isolated points   Then we must set 2 One exit is enough   Number of points in a connected block =cnt  Number of schemes =C[cnt][2] = cnt*(cnt-1)/2 2.2  Cut point  <=>  Point biconnected component   Shrinkage point ( Every cut point belongs to 2 Two point doubly connected components ) 2.2.1  First, all the cut points are separated as one point  2.2.2  From each point doubly connected components (V-DCC) Connect an edge to each cut point it contains  o o / \ / \ o---.---.---o \ / o  After shrinking point  .- Cut point  o- Connected block  o-.-o-.-o  At the same time, after shrinking o Contains previously connected  2.2.3  see V-DCC Degrees  2.2.3.1  If V-DCC==1  It means that it contains only one cut point ( Left and right in the above figure )  Then, if the cut point is an exit and breaks   This V-DCC You can't connect to other exits   therefore V-DCC==1  when   Must be in V-DCC Inside ( No cut point ) Place an exit  2.2.3.2  If V-DCC>1  There is no need to set an exit   prove : 1  If the cutting point breaks   After shrinking point , At this point all degrees ==1 The point of is equivalent to a leaf node - All degrees are 1 Put an exit on the leaf node of   Therefore, each leaf node must have an exit  .( Cut point ) ×/ \× o o( Connected block ) 2  If the degree is 1 On the right V-DCC Something in the is broken   Because it is V-DCC  After deleting the bad dot, it is still a V-DCC .( Cut point ) / \ o @( There is a broken point in the connected block )  But it doesn't affect this V-DCC To cut point   And to the left through the cut point V-DCC Exit from  3  If the degree is 2 Of V-DCC Something in the is broken   Because of the degree ==2 <=>  The two cut points must be connected  o( Connected block ) / \ . .( Cut point )  Every cut point must have an exit   So you can start from the top o To the next two cut points to the other V-DCC Find the exit   summary : 1  No cut point   discharge 2 An exit   Number of schemes  *= C[cnt][2] = cnt*(cnt-1)/2 2  Cut point  V-DCC==1  discharge 1 An exit   Number of schemes  *= C[cnt-1][1] = cnt-1 ( Do not include cut points ) 3  Cut point  V-DCC>=2  discharge 0 An exit   Number of schemes  *= 1 */

Code ：

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N]; //  You can't id  Because the repeating points belong to the connected components of different points 
bool cut[N];

void add(int a, int b)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void tarjan(int u, int root)
{
    
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;

    if (u == root && h[u] == -1) //  Special judgment point 
    {
    
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
    
        int j = e[i];
        if (!dfn[j])
        {
    
            tarjan(j, root);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j]) //  The branch of judgment 
            {
    
                cnt++;
                if (u != root || cnt > 1) // Judge the cut point 
                    cut[u] = true;

                /*  The essence of the stack is the edge ,（ In order of access ） A biconnected component of an edge belonging to only one point , A cut point belongs to the doubly connected components of multiple points ,  If the stack is a dot , When it pops up, this point can only give the biconnected component of one point . */
                dcc_cnt++;
                int y;
                do
                {
    
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);          //  therefore u Don't bounce out 
                dcc[dcc_cnt].push_back(u); //  add u
            }
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
}

int main()
{
    
    int T = 1;
    while (cin >> m, m)
    {
    
        for (int i = 1; i <= dcc_cnt; i++)
            dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(cut, 0, sizeof cut);

        while (m--)
        {
    
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
            n = max(n, a), n = max(n, b);
        }

        for (int i = 1; i <= n; i++)
        {
    
            if (!dfn[i])
                tarjan(i, i);
        }
        int res = 0;
        ULL num = 1;

        for (int i = 1; i <= dcc_cnt; i++)
        {
    
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j++) // Count the cut points in each connected block   That is, the degree after the shrinking point 
            {
    
                if (cut[dcc[i][j]])
                    cnt++;
            }

            if (cnt == 0)
            {
    
                if (dcc[i].size() > 1) //  A graph larger than two points has at least two exits 
                    res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else //  Special judgement 
                    res++;
            }
            else if (cnt == 1) //  A cut point   Then the point connected components are all except the cut points   Choose one of the other points 
                res++, num *= dcc[i].size() - 1;
            // Greater than 2  Don't change 
        }
        printf("Case %d: %d %llu\n", T++, res, num);
    }

    return 0;
}