Under construction

Still being built. Things may change

Free Edges

Time limit1sMemory limit512 MB

Summary
Given an undirected graph, find the minimum number of edges to paint black so that repeatedly blackening a white edge incident to a vertex with exactly one white edge turns every edge black.
Level

Hard8 of 10

Topics
Graph, DFS, Greedy, Tree
Solved
No attempts yet

Problem

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 nn and mm: the number of vertices and the number of edges in your graph (1≤n,m≤1051 \le n, m \le 10^5).

The next mm lines contain description of the edges of the graph. Each of these lines contains two integers aia_i and bib_i, describing an edge between vertices aia_i and bib_i (1≤ai,bi≤n1 \le a_i, b_i \le n, ai≠bia_i \ne 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.

Examples1

  1. Example 1

    Input
    5 3
    3 5
    5 1
    1 3
    
    Expected output
    1