#include<stdio.h>
#include<vector>
#include<deque>
#include<memory.h>
using namespace std;
int V,E;
vector<int> G[100001];
vector<int> rG[100001];
vector<int> vs;
bool used[100001];
int cmp[100001];
void add_edge(int from, int to)
{
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v)
{
used[v] = true;
for(int i=0;i<G[v].size();i++)
if(!used[G[v][i]])
dfs(G[v][i]);
vs.push_back(v);
}
void rdfs(int v,int k)
{
used[v]=true;
cmp[v] =k;
for(int i=0;i<rG[v].size();i++)
if(!used[rG[v][i]]) rdfs(rG[v][i],k);
}
int scc()
{
memset(used,0,sizeof(used));
vs.clear();
for(int v=0;v<V;v++)
if(!used[v])dfs(v);
memset(used,0,sizeof(used));
int k=0;
for(int i=vs.size()-1;i>=0;i--)
if(!used[vs[i]])rdfs(vs[i],k++);
return k-1;
}
int main()
{
scanf("%d %d",&V,&E);
for(int i=0;i<E;i++)
{ int tmp1,tmp2;
scanf("%d %d",&tmp1,&tmp2);
add_edge(tmp1,tmp2);
add_edge(tmp1,tmp2);
}
if(scc()==1)
printf("Not cactus\n");
else
printf("Cactus\n");
return 0;
}
