Stefan loves exploring forests but he usually gets lost in them. This time, he went a little too deep into the forest and no longer knows if he is even in a forest still. Help Stefan find out how many trees there are in the forest, or tell him that he is not in a forest anymore and is walking in circles. (Just to clarify, a forest is a graph that is not necessarily connected and contains no cycles. In other words, it is a collection of trees).

The first line contains two integers: N (The number of nodes in the graph) and M (The number of edges in the graph).

The next M lines contain two integers: u, v indicating that there is an undirected edge connecting the nodes u and v (1 ≤ u, v ≤ N)

If the graph given is a forest, print `Stefan is in a forest with T trees`

where T is the number of trees in the forest.

Otherwise, Stefan is walking in cycles, and you should print `middle of nowhere`

.

For all cases: 1 ≤ N, M ≤ 10^5

For batch 1 (30 points): 1 ≤ N ≤ 500

For batch 2 (10 points): Stefan is guaranteed to be in a forest

For batch 3 (60 points): No additional constraints

`9 6`

1 2

2 3

2 4

5 6

5 7

8 9

`Stefan is in a forest with 3 trees`

`7 6`

1 2

2 3

3 4

3 5

2 6

3 7

`Stefan is in a forest with 1 trees`

Explanation for Sample Case 2:

Stefan is in a forest with 1 tree (still considered a forest I guess)

`6 5`

1 2

2 3

3 1

4 5

5 6

`Middle of nowhere`

Explanation for Sample Case 3:

One of the components of the graph contains a cycle, so Stefan is no longer in a forest

- Points: 10
- Time limit: 2.0s
- Memory limit: 64.0M
- Author: jimmyliu
- Category: Classics
- Type: Graph Theory
- All Submissions Best Submissions

Comments

- There are no comments.