TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2311
  • 题目
  • P2311井下矿工
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    有一座地下的稀有金属矿由n条隧道和一些连接点组成,其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险,你的任务是在一些连接点处安装太平井和相应的逃生装置,使得不管哪个连接点倒塌,不在此连接点的所有矿工都能到达太平井逃生(假定除倒塌的连接点不能通行外,其他隧道和连接点完好无损)。为了节约成本,你应当在尽量少的连接点安装太平井。你还需要计算出在太平井的数目最小时的安装方案总数。

    输入格式

    输入包含多组数据。每组数据第一行为隧道的条数n(n<=50000),一下n行,每行两个整数,即一条隧道两段的连接点的编号(所有连接点从1开始编号)。每组数据的所有连接点保证连通。
    输入以数字0作为结束

    输出格式

    对于每组数据,输出两个整数,即最少需要暗转的太平井数目以及对应的方案总数。
    答案保证在64位带符号整数范围以内。

    样例输入

    9
    1 3
    4 1
    3 5
    1 2
    2 6
    1 5
    6 3
    1 6
    3 2

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

    样例输出

    Case 1: 2 4
    Case 2: 4 1


    来源  ACM/ICPC world finals 2011 Mining Your Own Business