#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
vector<int> node[100001];
vector<int> rv[100001];
bool chk[100001];
int group[100001];
int cnt[100001];
stack<int> st;
int ret;
int grp;
void dfs(int x)
{
chk[x] = true;
for(int i = 0 ;i < node[x].size();i++)
{
if( !chk[node[x][i]] )
dfs(node[x][i]);
}
st.push(x);
}
void dfs2(int x)
{
chk[x] = true;
group[x] = grp;
for(int i = 0 ;i < rv[x].size();i++)
{
if( !chk[rv[x][i]] ) {
cnt[rv[x][i]]++;
dfs2(rv[x][i]);
}
else if( group[rv[x][i]] == grp )
{
cnt[rv[x][i]]++;
}
}
}
int main(void){
int n, m;
scanf("%d %d",&n, &m);
for(int i = 0 ;i < m ;i++)
{
int a, b;
scanf("%d %d", &a, &b);
node[a].push_back(b);
rv[b].push_back(a);
}
memset(chk,0,sizeof(chk));
for(int i = 1; i <= n;i++)
{
if( !chk[i] )
dfs(i);
}
memset(cnt,0,sizeof(cnt));
memset(group, 0, sizeof(group));
memset(chk,0,sizeof(chk));
grp = 0;
while(!st.empty()){
int next = st.top();
st.pop();
if(!chk[next])
{
dfs2(next);
grp++;
}
}
for(int i = 1 ;i <=n ;i++)
{
int count = 0;
for(int j = 0 ;j < rv[i].size();j++)
{
if( group[rv[i][j]] == group[i] )
count++;
}
if( count > 1 )
{
printf("Not cactus\n");
return 0;
}
}
printf("Cactus\n");
return 0;
}
