#include <cstdio>
#include <vector>
using namespace std;
int N,M;
int visited_cnt;
void cnt_cycle(vector<vector<int> > &graph, int &cnt, vector<int> &visited, int pre, int now){
// printf("cycle now == %d, pre == %d, visited_cnt = %d\n", now, pre, visited_cnt);
if(visited_cnt > M) return ;
visited_cnt++; // count edge
if(visited[now] != 0){
// printf("now == %d\n", now);
cnt++;
return;
}
visited[now] = 1;
for(int i=0;i<graph[now].size();i++){
int to = graph[now][i];
if( pre != to)
cnt_cycle(graph, cnt, visited, now, to);
}
}
int main(){
scanf("%d%d",&N,&M);
vector<vector<int> > graph(N + 1);
for(int i=0;i<M;i++){
int a,b; scanf("%d%d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
int cnt = 0;
vector<int> visited(N+1, 0);
cnt_cycle(graph, cnt, visited, 0, 1);
if(cnt <= 1) printf("Cactus\n");
else printf("Not cactus\n");
return 0;
}
