#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 100001;
int N, M;
vector<int> adj[MAX_N];
bool isCactus = true;
int d[MAX_N]; vector<bool> visited; int cnt = 0;
int dfs(int u) {
visited[u] = true;
int ret = d[u] = cnt++;
int numBack = 0;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (!visited[v]) {
int res = dfs(v);
if (res < d[u]) {
numBack++;
ret = res;
}
}
if (d[v] != -1 && d[v] < d[u]) {
numBack++;
ret = min(ret, d[v]);
}
}
if (numBack > 2)
isCactus = false;
return ret;
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
memset(d, -1, sizeof(d));
visited = vector<bool>(N, false);
dfs(0);
if (isCactus)
printf("Cactus\n");
else
printf("Not cactus\n");
return 0;
}
