题目描述

When Leonhard Euler resolved the famous Königsberg bridge problem,he had no clue he had discovered a whole new area of mathematics -graph theory!

Unfortunately, the Königsberg bridge problem is far too easy for the programmers of this era, so Euler came up with another problem - the Zagreb bridge problem!

The bridges of Zagreb form a graph with $n$ nodes and $m$ edges where the edges represent the bridges and the nodes represent the riverine islands. The graph is connected, in other words, it’s possible to get from any node to any other by traveling across the edges. Now Euler asked, how many edges are there such that after their removal the graph becomes disconnected?

Again, Euler didn’t know that this problem is also famous today (those damn Codeforces blogs). So the author of this problem decided to give you an even harder one, how many edges are there such that after the removal of the nodes which it connects, the remaining $n − 2$ nodes become disconnected?

题目大意

给定一张 $n$ 个点 $m$ 条边的无向连通图，求有多少条边满足删去这条边两端的两个点之后，剩余的 $n-2$ 个点不连通。

输入格式

一行两个正整数 $n,m$ 分别表示点数和边数。

接下来一行每行两个正整数 $a_i,b_i$ 表示有一条边连接 $a_i,b_i$。

输出格式

一行一个整数表示符合条件的边的数量。

4 5
1 2
2 3
3 4
4 1
1 3

1

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

4

提示

【样例解释#1】

对于边 $(1,3)$，删去它和对应的点 $1,3$ 之后，包含两个连通块，分别包括节点 $2$ 和 $4$，也就是说，图不连通了。容易验证这是唯一满足条件的边。

【样例解释#2】

满足条件的边有：$(1, 2), (2, 4), (2, 6) , (2, 5)$。

【数据范围】

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq3\times10^5$，$1\leq a_i,b_i\leq n$，图中无重边、自环。

本题采用捆绑测试。

【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2022-2023 CONTEST #1 T5 Mostovi。