#P1780. 2024.03.31-ZJTD-第一题-基环树

2024.03.31-ZJTD-第一题-基环树

题目描述

定义基环树为个点、条边且不包含重边和自环的无向连通图。形象化的描述，基环树可以由一棵树再添加一条边后形成(不能是树上已存在的边)现在塔子哥拿到了一个无向图，她想连一条边使得这个无向图变成基环树。塔子哥想知道，有多少种不同的连边方案?

输入描述

第一行输入两个正整数n,mn,m，代表无向图的点数和边数。

接下来的mm行，每行输入两个正整数u,vu,v，代表节点uu和节点vv有一条边连接。保证给定的无向图不包含重边和自环。

1≤n,m≤1051\le n,m\le 10^5

1≤u,v≤n1\le u,v\le n

输出描述

一个整数，代表添加边的方案数。

样例1

输入

4 4
1 2
1 3
2 3
2 4

输出

0

说明

本身该无向图已经是基环树，因此方家数为 0。

样例2

输入

4 3
1 2
1 3
2 3

输出

3

说明

第一个方案:连接1和4。
第二个方案:连接2和4。
第三个方案:连接3和4。

知识点:*****

查看知识点以及同类型题目

Statistics