Trees

Interview

Time limit1sMemory limit256 MB

Summary

Given an undirected graph, count its connected components that contain no cycle and report the count per test case.

Level: Medium5 of 10
Topics: Graph, Union-find, DFS, Implementation
Solved: No attempts yet

Problem

A graph consists of vertices and edges. If there is a path between two vertices, those two vertices are said to be connected. A connected component is a subset of vertices in which every vertex is connected to every other vertex, and a graph is made up of one or more connected components.

A tree is a connected component that has no cycle. A tree has several properties. For example, a tree with $n$ vertices has exactly $n-1$ edges, and the path between any two vertices is unique.

Given a graph, write a program that counts the number of trees in it. A connected component consisting of a single vertex has $0$ edges and therefore no cycle, so it is also counted as a tree.

Input

The input consists of several test cases. The first line of each test case contains the number of vertices $n$ and the number of edges $m$ , satisfying $n \le 500$ and $m \le n(n-1)/2$ . Each of the following $m$ lines contains two integers describing an edge. No edge is given more than once. Vertices are numbered from $1$ to $n$ . The last line of the input contains two zeros.

Output

For each test case, print one line. Print No trees. if the graph contains no tree, There is one tree. if it contains exactly one, and A forest of T trees. if it contains $T$ trees ( $T > 1$ ), where T is the number of trees. Each line begins with Case X: , where $X$ is the test case number starting from $1$ .

Examples4

Example 1

Input

Expected output

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

Example 2
Input
```
1 0
0 0
```
Expected output
```
Case 1: There is one tree.
```
Example 3
Input
```
3 0
0 0
```
Expected output
```
Case 1: A forest of 3 trees.
```
Example 4
Input
```
3 3
1 2
2 3
3 1
0 0
```
Expected output
```
Case 1: No trees.
```