406113: GYM102268 F Free Edges

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Free Edgestime limit per test1 secondmemory limit per test256 mebibytesinputstandard inputoutputstandard output

You have an undirected graph. Initially, all edges are white. You can choose some edges and paint them black.

After that, while there is a vertex such that exactly one white edge comes out of it, this white edge also becomes black.

Your goal is to choose the minimum possible number of edges to paint black such that, after the process is finished, all edges will be black.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$: the number of vertices and the number of edges in your graph ($$$1 \leq n, m \leq 10^5$$$).

The next $$$m$$$ lines contain description of the edges of the graph. Each of these lines contains two integers $$$a_i$$$ and $$$b_i$$$, describing an edge between vertices $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$).

It is guaranteed that there are no multiple edges.

Output

Print one integer: the minimum possible number of edges you need to paint black such that, after the end of the described process, all edges will be black.

ExampleInput
5 3
3 5
5 1
1 3
Output
1

Source/Category

加入题单

算法标签: