#include<stdio.h>
#include<vector>
using namespace std;
vector<int> edge[100000];
vector<int> now;
bool check[100000]={0};
bool check_cycle[100000]={0};
bool ans=false;
int distime[100000]={0},deltime[100000]={0},time=0;
void dfs(int a,int par){
check[a]=true;
distime[a]=time++;
now.push_back(a);
int i,j;
for(i=0;i<edge[a].size();i++){
if(check[edge[a][i]] && edge[a][i]!=par && distime[edge[a][i]]<distime[a]){
if(check_cycle[edge[a][i]]){
ans=true;
return;
}
else{
for(j=now.size()-1;j>=0;j--){
check_cycle[now[j]]=true;
if(now[j]==edge[a][i]) break;
}
}
}
else if(!check[edge[a][i]]){
dfs(edge[a][i],a);
if(ans) return;
}
}
deltime[a]=time++;
now.pop_back();
}
int main()
{
int i,n,m,a,b;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
edge[a-1].push_back(b-1);
edge[b-1].push_back(a-1);
}
dfs(0,0);
if(ans) printf("Not cactus");
else printf("Cactus");
return 0;
}
