Independent Cycles

Difficulty: 1600 4000 ms 128 MB

math graphs union-find

Print the dimension of the graph's cycle space: the maximum number of independent cycles (equivalently, edges you must delete to make it a forest). Multi-edges and self-loops count.

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

Output: M − N + (number of components) — computed correctly for multigraphs.

Constraints:

• 1 ≤ N, M ≤ 10⁵

Sample Tests

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

2

2 1
1 2

0

Read the Editorial