선인장인지 판정하기

선인장은 무방향 그래프의 한 종류로, 어느 정점을 골라도 그 정점을 지나 자기 자신으로 돌아오는 단순 사이클이 하나 이하인 그래프다. 단순 사이클은 같은 정점을 두 번 지나지 않고 출발한 정점으로 돌아오는 경로를 뜻한다.

두 사이클이 정점 하나를 공유하면 그 정점을 지나는 단순 사이클이 둘이 되므로 선인장이 아니다. 삼각형 두 개가 정점 하나만 맞대고 있는 그래프도 조건을 만족하지 못한다.

연결 그래프가 주어진다. 이 그래프가 선인장인지 판정하라.

첫째 줄에 그래프의 정점 개수 $N$과 간선 개수 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 100\,000$)

다음 $M$개 줄에는 간선이 잇는 두 정점의 번호 $x$와 $y$가 공백으로 구분되어 주어진다. ($1 \le x, y \le N$, $x \ne y$)

같은 간선이 두 번 주어지지 않으며, 어떤 두 정점 사이에도 경로가 존재한다.

주어진 그래프가 선인장이면 Cactus를, 아니면 Not cactus를 출력한다.