Forest X41530


Statement
 

pdf   zip

html

A forest is a graph without cycles, and each of its connected components is a tree. Given an undirected graph, is it a forest? In case it is, how many trees does it have?

Input

Input consists of several graphs. Every graph starts with its number of vertices n and its number of edges m, followed by m pairs x y indicating an edge between vertices x and y. Assume 1 ≤ n ≤ 104, 0 ≤ m < n, that vertices are numbered from 0 to n−1, and that there are neither repeated edges nor edges of the type x x.

Output

For every graph, if it is a forest print the number of trees it has. Otherwise, print “no”.

Public test cases

  • Input

    1 0
2 1  1 0
2 0
4 3  0 1  1 2  0 2
8 6  0 4  5 3  3 1  3 7  2 4  6 0
8 6  0 1  2 1  3 4  4 5  5 3  7 6
10 9  0 1  0 2  1 3  1 4  2 5  2 6  3 7  3 8  3 9

    Output

    1
1
2
no
2
no
1
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Albert Atserias
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++