#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
vector<int> G[100010],C[100010]; int Q[100010]; bool chk[100010];
int N,M;
void in(int x, int y)
{
C[x].push_back(y);
C[y].push_back(x);
}
int Depth[100010],Low[100010];
stack<pair<int, int> > S;
int main()
{
int i,j,x,y;
scanf ("%d %d",&N,&M);
for (i=0;i<M;i++){
scanf ("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
S.push(make_pair(1,-1)); Depth[1] = Low[1] = 1;
while (!S.empty()){
x = S.top().first; i = S.top().second; S.pop();
if (i >= 0){
if (Low[x] > Low[G[x][i]])
Low[x] = Low[G[x][i]];
}
for (i++;i<G[x].size();i++){
y = G[x][i];
if (Depth[y] == 0){
Depth[y] = Low[y] = Depth[x] + 1;
S.push(make_pair(x,i));
S.push(make_pair(y,-1));
break;
}
else{
if (Depth[y] + 1 < Depth[x]){
in(x,y);
if (Low[x] > Depth[y])
Low[x] = Depth[y];
}
}
}
if (i == G[x].size() && !S.empty()){
if (Low[x] <= Depth[S.top().first]){
in(x,S.top().first);
}
}
}
for (i=1;i<=N;i++) if (!chk[i]){
int head = -1, tail = -1;
int V = 0, E = 0;
Q[++head] = i; chk[i] = 1;
while (tail < head){
x = Q[++tail];
V++; E += C[x].size();
for (j=0;j<C[x].size();j++){
y = C[x][j];
if (!chk[y]){
Q[++head] = y; chk[y] = 1;
}
}
}
if (V * 2 < E){puts("Not cactus"); return 0;}
}
puts("Cactus");
return 0;
}
