Free Edges

시간 제한1초메모리 제한512 MB

요약

무방향 그래프가 주어질 때, 흰 간선이 하나만 나오는 정점에서 그 간선을 검게 칠하는 과정을 반복해 모든 간선이 검게 되도록 처음에 검게 칠할 간선 수의 최솟값을 구한다.

문제

무방향 그래프가 있다. 처음에는 모든 간선이 흰색이다. 여러분은 몇몇 간선을 골라 검은색으로 칠할 수 있다.

그다음, 어떤 정점에서 흰색 간선이 정확히 하나만 나오는 동안, 그 흰색 간선도 검은색이 된다.

목표는 과정이 끝난 뒤 모든 간선이 검은색이 되도록, 검은색으로 칠해야 하는 간선의 수를 최소로 하는 것이다.

첫째 줄에 정점의 수 $n$ 과 간선의 수 $m$ 이 주어진다 ( $1 \le n, m \le 10^5$ ).

다음 $m$ 개의 줄에는 그래프의 간선이 주어진다. 각 줄에는 두 정수 $a_i$ 와 $b_i$ 가 주어지며, 정점 $a_i$ 와 $b_i$ 를 잇는 간선을 나타낸다 ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ ).

중복 간선은 없다.

과정이 끝난 뒤 모든 간선이 검은색이 되도록 검은색으로 칠해야 하는 간선 수의 최솟값을 정수 하나로 출력한다.