A city power grid is an undirected graph with n stations (0 to n-1) and m cables. A cable is a weak link if removing it increases the number of connected components — that is, some pair of stations that were connected can no longer reach each other. A cable that is not a weak link is resilient: the grid stays exactly as connected without it.
Count the resilient cables.
Definitions for multi-edges and self-loops:
- A self-loop (
u == v) is always resilient (removing it never disconnects anything). - If two or more cables directly join the same pair of stations, none of those parallel cables is a weak link (each is resilient), because removing one leaves the pair joined by another.
Equivalently: a cable is a weak link exactly when it is a bridge, and you must count the cables that are not bridges. Count cables, so parallel cables between the same pair are counted separately.
Input format
Line 1: two integers n and m.
Next m lines: two integers u v (0-indexed) — a cable between u and v.
Output format
A single integer: the number of resilient (non-bridge) cables.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ m ≤ 200000
- 0 ≤ u, v ≤ n-1
- Self-loops and parallel edges may appear.