Bosc X41530

Statement

html

Un bosc és un graf sense cicles, i cada component connexa és un arbre. Donat un graf no dirigit, és un bosc? I, en aquest cas, quants arbres té?

Entrada

L’entrada consisteix en diversos grafs. Cadascun comença amb el nombre de vèrtexs n i el nombre d’arestes m, seguits de m parells x y que indiquen una aresta entre els vèrtexs x i y. Suposeu 1 ≤ n ≤ 10⁴, 0 ≤ m < n, que els vèrtexs es numeren entre 0 i n−1, i que no hi ha arestes repetides ni de tipus x x.

Sortida

Per a cada graf, si és un bosc escriviu el seu nombre d’arbres. Altrament, escriviu “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: Catalan
Other languages: English
Official solutions: Unknown. This problem is being checked.
User solutions: C++