Cactus or not

Interview

Time limit1sMemory limit32 MB

Summary

Decide whether a connected undirected graph is a cactus where each vertex lies on at most one simple cycle.

Level: Medium5 of 10
Topics: DFS, Graph
Solved: No attempts yet

Problem

A cactus is an undirected graph in which every vertex lies on at most one simple cycle. A simple cycle is a closed walk that returns to the vertex it started from without visiting any vertex twice.

If two cycles share a vertex, that vertex lies on two simple cycles, so the graph is not a cactus. Two triangles that meet at a single vertex already fail the condition.

You are given a connected graph. Decide whether it is a cactus.

Input

The first line contains two integers $N$ and $M$ , the number of vertices and the number of edges, separated by a space. ( $1 \le N, M \le 100\,000$ )

Each of the next $M$ lines contains two integers $x$ and $y$ , the endpoints of one edge, separated by a space. ( $1 \le x, y \le N$ , $x \ne y$ )

No edge is given twice, and a path exists between every pair of vertices.

Output

Print Cactus if the given graph is a cactus, and Not cactus otherwise.

Examples8

Example 1
Input
```
4 4
1 2
2 3
3 1
3 4
```
Expected output
```
Cactus
```
Example 2
Input
```
5 6
1 2
2 3
3 1
3 4
4 5
5 3
```
Expected output
```
Not cactus
```
Example 3
Input
```
2 1
1 2
```
Expected output
```
Cactus
```
Example 4
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
Cactus
```
Example 5
Input
```
5 6
1 2
2 3
3 1
1 4
4 5
5 1
```
Expected output
```
Not cactus
```
Example 6
Input
```
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
```
Expected output
```
Cactus
```
Example 7
Input
```
4 6
1 2
1 3
1 4
2 3
2 4
3 4
```
Expected output
```
Not cactus
```
Example 8
Input
```
4 5
1 2
2 3
3 4
4 1
1 3
```
Expected output
```
Not cactus
```