#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top=-1,stack[100001];
using namespace std;
vector<int> list[100001],list2[100001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
int i;
check[k]=1;
for(i=0;i<list[k].size();i++){
if(!check[list[k][i]]){
list2[list[k][i]].push_back(k);
edge.insert(make_pair(make_pair(list[k][i],k),false));
back(list[k][i]);
}
else if(edge.find(make_pair(k,list[k][i]))==edge.end()){
edge.insert(make_pair(make_pair(list[k][i],k),true));
list2[list[k][i]].push_back(k);
}
}
stack[++top]=k;
}
void flood(int k){
int i;
check[k]=1;
for(i=0;i<list2[k].size();i++){
if(!check[list2[k][i]]){
it=edge.find(make_pair(k,list2[k][i]));
if(it->second){
if(backedge)
flag=1;
backedge=1;
}
flood(list2[k][i]);
}
}
stack[++top]=k;
}
int main(){
int m,i,a,b;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++){
scanf("%d %d",&a,&b);
a--;b--;
list[a].push_back(b);
list[b].push_back(a);
}
for(i=0;i<n;i++){
if(!check[i])
back(i);
}
memset(check,0,sizeof(check));
for(;top>=0;top--){
backedge=0;
if(!check[stack[top]])
flood(stack[top]);
}
if(flag)
printf("Not cactus\n");
else
printf("Cactus\n");
return 0;
}
