Critical Wires

Difficulty: 1900 4000 ms 128 MB

graphs

A bridge is an edge whose removal disconnects its endpoints. Count the bridges of the undirected graph (multi-edges between the same pair are never bridges).

Input: the first line has N and M; each of the next M lines has an edge u v.

Output: the number of bridges.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴

Sample Tests

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

2

2 2
1 2
1 2

0

Read the Editorial