COCI '23 Contest 1 #5 Mostovi

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

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?

Input Specification

The first line contains integers n and m (4 \le n \le 100\,000, n-1 \le m \le 300\,000), the number of nodes and edges respectively.

Each of the next m lines contains integers a_i and b_i (1 \le a_i, b_i \le n), meaning nodes a_i and b_i are connected with an edge.

There are no loops or multiple edges.

Output Specification

In a single line, output the number of edges with the given property.


Subtask Points Constraints
1 13 n \le 100, m \le 300
2 17 n \le 1 000, m \le 3\,000
3 25 n \le 1\,000
4 12 m-n \le 20
5 43 No additional constraints.

Sample Input 1

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

Sample Output 1


Explanation for Sample 1

By removing edge (1, 3) and corresponding nodes 1 and 3, the remaining graph has two connected components, node 2 and node 4. In other words, it is not connected. It is easy to check that this is the only edge with this property.

Sample Input 2

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

Sample Output 2


Explanation for Sample 2

The edges with the required property are (1, 2), (2, 4), (2, 6) and (2, 5).


There are no comments at the moment.