P9907 [COCI 2023/2024 #1] Mostovi

Abusing the judging system for this problem will result in an account ban.

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 programmers nowadays, 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 river islands. The graph is connected; in other words, it is possible to get from any node to any other by traveling along the edges. Now Euler asked: how many edges are there such that after removing them, the graph becomes disconnected? Again, Euler did not know that this problem is also well known 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 removing the two nodes it connects, the remaining $n - 2$ nodes become disconnected? ### Main idea Given a connected undirected graph with $n$ nodes and $m$ edges, find how many edges satisfy that after deleting the two endpoints of this edge, the remaining $n - 2$ nodes are disconnected.

The first line contains two positive integers $n, m$, representing the number of nodes and edges. Each of the next $m$ lines contains two positive integers $a_i, b_i$, meaning there is an edge connecting $a_i$ and $b_i$.

Output one integer, the number of edges that satisfy the condition.

### Sample Explanation #1 For the edge $(1, 3)$, after deleting it and the corresponding nodes $1, 3$, there are two connected components, containing nodes $2$ and $4$ respectively. That is, the graph becomes disconnected. It is easy to verify that this is the only edge that satisfies the condition. ### Sample Explanation #2 The edges that satisfy the condition are: $(1, 2), (2, 4), (2, 6), (2, 5)$. ### Constraints For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 3 \times 10^5$, $1 \leq a_i, b_i \leq n$. There are no multiple edges or self-loops in the graph. **This problem uses bundled tests.** | Subtask | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $n \leq 100$, $m \leq 300$ | $13$ | | $2$ | $n \leq 1000$, $m \leq 3000$ | $17$ | | $3$ | $n \leq 1000$ | $25$ | | $4$ | $m - n \leq 20$ | $12$ | | $5$ | No special property | $43$ | ### Notes The score of this problem follows the original COCI setting, with a full score of $110$. Translated from [COCI2023-2024](https://hsin.hr/coci/archive/2023_2024/) [CONTEST #1](https://hsin.hr/coci/archive/2023_2024/contest1_tasks.pdf) _**T5 Mostovi**_。 Translated by ChatGPT 5