logo AlgoBeat OnlineJudge
登录 注册

#102519. [BZOJ 2519] [Shoi2010]电脑网络

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

SHOI 的领队为了方便大家交流,决定在大家集训的机房里建立起一个局域网络。现在的机房里一共有n台电脑终端, SHOI 的领队使用了 条网线去建立这个局域网,每条网线都把某两台电脑连接起来使得它们可以双向通信。现在这个网络是连通的,也就是说,任意两台电脑之间都可以直接的或间接的通信。 为了在整个备战过程中,确保所有学生之间通过这个电脑网络的交流, SHOI 的领队想要知道:“如果某台电脑 A 因故障关机的同时某一条网线 (并非连接在A上的)被切断,那么,除了 A 以外的其他电脑能否保持相互通信?” 于是, SHOI 的领队需要你计算这个局域网络的“不稳定程度”。不稳定程度是指:通过从网络中移除一台电脑且切断一条网线(这条网线不连接在这台电脑上)使得整个网络中的其他电脑之间通讯不完全连通的不同方案的总数。

输入格式

输入文件的第一行有两个正整数 ,分别表示网络中的电脑终端的数量以及用来连接电脑的网线数量。 接下来 行每行有两个整数 来描述一条网线,表示这条网线连接了编号为 的电脑,且。 输入文件保证,这个电脑网络初始时是连通的。

输出格式

输出文件只有一行,这行只有一个整数,即为通过从网络中移除一台电脑且切断一条网线使得整个网络不连通的不同方案总数。

样例

样例输入 #1

5 4
1 2
1 3
1 4
1 5

样例输出 #1

12

数据范围与提示

day1